📌난이도🥈4

📌코드

📘 List + Dict

import sys
input = sys.stdin.readline

nl = []
ns = dict()
answer = []

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

for i in range(N+M):
    if i < N:
        nl.append(input().rstrip())
    else:
        ns[input().rstrip()] = 1


nl.sort()

for i in nl:
    if i in ns:
        answer.append(i)

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

Dict 에서 in 은 시간복잡도가 O(1)이기 때문에 list 2개로 == ( 시간복잡도 O(N) )을 사용하는 것 보다 빠르다.

📘 set

import sys
input = sys.stdin.readline

nl = []
ns = dict()
answer = []

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

a = set()
b = set()

for i in range(N):
    a.add(input().rstrip())

for i in range(M):
    b.add(input().rstrip())

answer = sorted(list(a & b))

print(len(answer))

for i in answer:
    print(i)

📌후기

• in 의 시간복잡도에 대해서 알게 되었고
• set 안에 & , | , - 있는것을 다시 떠올리게 되었다 .

검색할때

• == : 시간복잡도가 list에서 O(N) ..
• 중첩 for : O(N^2)
• Dict

이렇게 까지만 생각났었는데 set도 방법으로 추가

🙄 자료형들에 대한 시간복잡도를 한번 정리해보자