1764번 - 듣보잡

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

문제 입력을 고려하지 않고 리스트로 구현했다가 시간초과가 났다.

파이썬의 자료구조 중 dictionary를 사용하여 구현하였다.

딕셔너리에서 키를 검색하는 방법(key in dict)의 시간 복잡도는 O(1)이지만, 리스트(elem in list)는 O(n)이기 때문에 훨씬 효율적이다. 딕셔너리와 리스트의 주요 연산 시간 복잡도 비교는 아래의 링크에서 더 자세하게 확인할 수 있다. (감사합니다)

https://velog.io/@kimwoody/Python-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%99%80-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC%EC%9D%98-%EC%A3%BC%EC%9A%94-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Python] 리스트와 딕셔너리의 주요 연산 시간 복잡도

따라서! 딕셔너리를 사용하면 더 효율적으로 문제를 해결할 수 있다.

# 듣보잡
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = dict()
answer = []
for _ in range(N):
    name = input().rstrip()
    arr[name] = 1 # 듣도 못한 사람
for _ in range(M):
    name = input().rstrip()
    if name in arr: # 듣도 보도 못한 사람
        answer.append(name)
answer.sort() # 정렬
print(len(answer))
print('\n'.join(answer))