うわさ話

質問する

白俊1764号助聴器

に答える

最初はリストで解いたが、タイムアウトした.in演算を使えば、時間の複雑さはどの資料構造とも同じだと思っていたが、違う.

list, tuple

Average : O(n)
ひとつひとつ巡回するのでO(n)のような時間的複雑さがある

set, dictionary

Average : O(1), Worst : O(n)
内部はhashにより格納されるため,アクセス時間はO(1)である.しかしながら、ハッシュ競合によりパフォーマンスが低下する場合、O(n)が必要となる場合がある.
探索後,集合,ディクシャナ演算の時間的複雑度はO(1)であることが分かった.
聞いたことのない人は全部でlisten人です.
次のm行の入力に見られない人seeがlistenにある場合、リスト듣보잡に追加されます.
集合資料型を使用していたので、期間限定で通過しました.

import sys

n, m = map(int, sys.stdin.readline().split())
listen = set(sys.stdin.readline() for _ in range(n))
듣보잡 = []
for _ in range(m):
    see = sys.stdin.readline()
    if see in listen:
        듣보잡.append(see)
듣보잡.sort()
print(len(듣보잡))
print(''.join(듣보잡))