[백준/Python] 14425번 문자열 집합 문제

■ 14425번 문자열 집합 문제

 

출처: 백준 14425번 문자열 집합 문제

 

 

■ 코드 풀이

 

처음에는 리스트를 활용하여 풀었습니다. 시간 초과는 나오지 않았지만, 상당히 시간이 오래 걸렸습니다. 코드 개선을 위해 다른 분들의 글을 참고하니, 재미있는 사실을 발견했습니다.

 

import sys

N, M = map(int, sys.stdin.readline().split())

S = []
count = 0

for _ in range(N):
    word = sys.stdin.readline().strip()
    S.append(word)

for _ in range(M):
    check = sys.stdin.readline().strip()
    if check in S:
        count +=1
        
print(count)

 

파이썬에서는 set 또는 딕셔너리와 같은 자료형이 리스트 대비 빠르다고 합니다. 이유는 set과 딕셔너리가 해시 테이블(hash table)을 활용하기 때문이라고 하는데요. 쉽게 말하면, 어떤 임의의 단어를 숫자로 맵핑하고 이 숫자를 인덱스처럼 활용하기 때문에 속도가 빠르다고 합니다. 즉, 이번 문제처럼 문자열 탐색의 경우에는 더욱 유용하게 사용될 수 있습니다.

 

그래서 코드를 아래와 같이 개선했습니다. 

 

import sys

N, M = map(int, sys.stdin.readline().split())

S = dict()
count = 0

for _ in range(N):
    word = sys.stdin.readline()
    S[word] = True

for _ in range(M):
    check = sys.stdin.readline()
    if check in S.keys():
        count+=1

print(count)

 

이제 두 코드의 속도를 비교해 보겠습니다. 아래 이미지를 보시면 리스트를 활용한 코드는 3740ms가 걸렸고 딕셔너리 코드는 116ms밖에 걸리지 않았습니다. 문자열 탐색에 대해서는 속도 차이가 정말 엄청나네요. 저도 좋은 공부가 되었습니다. 참고로 파이썬 set과 딕셔너리의 해시 테이블 관련 내용에 대해 제가 참고한 글의 링크를 아래에 넣어두었으니 더 공부하실 분들은 들어가 보시면 도움이 될 것 같습니다.

 

풀이 #1과 풀이 #2의 비교: 딕셔너리가 리스트보다 훨씬 빠르다

 

 

[참고] 파이썬 set과 딕셔너리가 빠른 이유

 

https://analytics4everything.tistory.com/180

Set, Dict의 자료구조가 검색이 빠른 이유? hash 함수