백준 14425

중복 없는 n개의 문자열이 담긴 집합 s가 주어질 때,
m개의 문자열 중 집합 s에 포함된 문자열의 개수를 구하는 문제이다.

중복이 없기 때문에 리스트와 for문으로 쉽게 해결할 수 있다.

코드(정답)는 다음과 같다.

# 14425

import sys

n, m = map(int, sys.stdin.readline().split())

s = []
for _ in range(n):
    s.append(sys.stdin.readline().rstrip())

cnt = 0
for _ in range(m):
    check_str = sys.stdin.readline().rstrip()

    if check_str in s:
        cnt += 1

print(cnt)

파이썬에서 리스트보다 집합(Set), 딕셔너리(Dictionary)의 검색이 더 빠르다.
이는 해시 테이블을 이용하기 때문이다.

위의 코드를 집합 자료형으로 바꾸어 푸는 것은 간단하다.

import sys

n, m = map(int, sys.stdin.readline().split())

s = set()
for _ in range(n):
    s.add(sys.stdin.readline().rstrip())

cnt = 0
for _ in range(m):
    check_str = sys.stdin.readline().rstrip()

    if check_str in s:
        cnt += 1

print(cnt)

결과는 같지만.. 속도 측면에서 꽤나 큰 차이가 난다.

해시 테이블을 이용한 검색이 빠른 이유에 대해선 아래의 블로그의 내용을 읽어보며 정리했다.

https://analytics4everything.tistory.com/180