[백준] 14425 문자열 집합 - Python

문제

https://www.acmicpc.net/problem/14425
문자열이 저장된 두개의 리스트 혹은 딕셔너리를 만들어주고, 같은 문자열이 있는 경우를 판별해주면 해결할 수 있는 문제였습니다. 그러나, 이 문제는 해시로 구현된 딕셔너리를 활용하면 데이터를 탐색하는데 시간 복잡도가 O(1)이기 때문에 시간 복잡도를 줄일 수 있습니다.

[Python] - 리스트 활용 시

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
s = [input() for _ in range(n)]
will_check=[input() for _ in range(m)]

count = 0

for i in will_check:
    if i in s:
        count+=1
print(count)

[Python] - 딕셔너리 활용 시

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
s = dict()
count = 0

for _ in range(n):
    s[input()] = True

for _ in range(m):
    if input() in s.keys():
        count+=1
print(count)

결과

위와 같이 딕셔너리를 활용할 경우 시간 복잡도가 현저히 줄었음을 알 수 있습니다.