[백준] 14425번 문자열 집합 - 파이썬

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

14425번: 문자열 집합

풀이

시간초과에 주의해서 문제를 풀어줘야합니다.

주어지는 N개의 문자열을 리스트가 아닌 집합에 넣어서 처리해야합니다.

리스트는 순열 순회를 해서 요소를 찾지만 집합은 해시테이블을 이용해서 요소를 찾기에 소모되는 시간의 차이가 있습니다.

집합을 통해서 검색하는 과정은 시간복잡도가 O(1)이 소모되지만, 리스트는 O(N)이 소모됩니다.

 

# 14425 문자열 집합
import sys
n, m = map(int,input().split())
ans = 0

s  = set([sys.stdin.readline() for i in range(n) ])

for _ in range(m):
    word = sys.stdin.readline()
    if word  in s:
            ans += 1
    
print(ans)

출력결과