백준 1764번: 듣보잡

백준 1764번: 듣보잡

아이디어

list에 집어넣고 하나하나 비교하면 O(N^2)로 시간 안에 해결할 수 없다.
hash set는 탐색에 걸리는 시간이 O(1)이기 때문에 시간 안에 해결할 수 있다.
파이썬에서는 set 자료구조를 제공한다.

코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())

dSet = {input().rstrip() for _ in range(N)}
bSet = {input().rstrip() for _ in range(M)}
dbList = list(dSet & bSet) //교집합
dbList.sort()

print(len(dbList))
for i in dbList:
    print(i)

여담

파이썬 set의 교집합 method(intersection)의 시간복잡도는 O(len(a) + len(b))이다.