1764번 듣보잡

문제 출처 : https://www.acmicpc.net/problem/1764

간단한 문제. Just 비교지만 이론적으로 알아두고 짚고 갈 부분이 있어 글을 씁니다.

1. 분명한 건 pop(0)는 O(n)의 시간복잡도를 가지고, deque에서 popleft는 O(1)의 시간은 소비하기 때문에 시간복잡도 면에 있어 훨씬 빠르다.

2. python에는 list,set,dict,tuple등의 자료구조가 있다.
   크게 생각하면
   list : 데이터 수정, iterable
   tuple : Only 읽기,immutable
   set : 중복불허, 순서불필요
   dict : ...

이때 in 을 자주 사용할텐데 list에서는 in을 사용할때 평균 O(n)의 시간이 걸리지만 set의 경우 O(1)의 시간이 걸리기 때문에 매우 빠르다. ( dict도 마찬가지로 O(1) )

import sys

N, M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
nl=set()
for n in range(N) :
    nl.add(sys.stdin.readline().rstrip("\n"))

nw = []
nlw = []
for m in range(M) :
   nw.append(sys.stdin.readline().rstrip("\n")) 
   if nw[-1] in nl :
       nlw.append(nw[-1])
nlw.sort()
print(len(nlw))
for i in nlw :
    print(i)

위 코드를 set으로 실행하면 성공하지만 nl을 list로 바꿔서 실행하면 시간 초과가 난다.