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

1. 문제

 

 

 

2. 코드

원래 코드 (list 사용)

n, m = map(int, input().split())

s = []
cnt = 0

for i in range(n):
    s.append(input())
for i in range(m):
    test = input()
    for j in range(n):
        if test == s[j]:
            cnt+=1

print(cnt)

 

정답 코드 (set 사용)

n, m = map(int, input().split())

s = set()
cnt = 0

for i in range(n):
    s.add(input())
    
for i in range(m):
    test = input()
    if test in s:
        cnt +=1 
print(cnt)

 

 

 

 

3. 주요 알고리즘

파이썬에서는 자료구조( list, set, dict, etc )에 따라 시간 복잡도가 다르다.

set, dict은 해쉬 테이블 구조를 사용한다. 이 때, 해쉬 테이블 구조는 key 값으로 데이터를 받아오므로 list 같은 구조보다 훨씬 빠르다.

따라서 이 문제에서는 list보다 빠른 set이나 dict 자료형을 사용해야 한다.