1764. 듣보잡

문제

백준 1764번 듣보잡

---

풀이

처음엔 리스트를 사용해서 풀었는데 시간초과났다.

어차피 in 연산을 쓰는거면 시간복잡도는 어느 자료구조나 똑같을 줄 알았는데 달랐다..

list, tuple

Average : O(n)
하나하나 순회하기 때문에 O(n)만큼의 시간복잡도를 갖는다

set, dictionary

Average : O(1), Worst : O(n)
내부적으로 hash를 통해 저장하므로 접근하는 시간은 O(1)이다. 하지만 해쉬의 충돌이 많아 성능이 떨어지는 경우 O(n)이 걸릴 수도 있다.

검색해보니 집합, 딕셔너리는 in 연산의 시간복잡도가 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(듣보잡))