자료구조의 중요성 (실버 4)

#1764번 듣보잡 https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

처음에 대충 풀었더니 시간초과나길래 고민을 좀 했다.

 

딕셔너리에서 key로 값을 호출하는 시간복잡도가 O(1)이길래

딕셔너리를 활용했다.

N, M = map(int, input().split())
nonlisten = dict()

for _ in range(N):
    nonlisten[input()] = False

for _ in range(M):
    try:
        s = input()
        if not nonlisten[s]:
            nonlisten[s] = True
    except:
        continue

answer = [key for key in nonlisten if nonlisten[key]]
print(len(answer))
for a in answer:
    print(a)

답은 맞았다.

 

하지만 더욱 정석적인 풀이는 집합연산이다.

 

N, M = map(int, input().split())
nonlisten = set(input() for _ in range(N))
nonsee = set(input() for _ in range(M))
answer = sorted(nonlisten & nonsee)
print(len(answer))
for i in answer:
    print(i)

합집합 연산자 A & B ( A.intersection(B) ) 를 사용하여 풀이한다.

 

나는 이 방법을 떠올리지도 못했지만 처음 봤을 당시 시간복잡도가 꽤 크지 않을까 라는 생각을 했었다.

 

실제 시간은 O( A길이  + B길이 ) 이다. 시간복잡도는 내 풀이와 크게 다르지 않다고 생각한다.

 

in만 사용하지 않으면 될 듯 하다.

in을 사용한 풀이는 O(A의 길이 X B의 길이) 가 되기 때문이다.