[BOJ] [python] 1764: 듣보잡 -해시 테이블과 시간복잡도

 

문제 풀이

---

문제 자체는 어렵지 않아서 보이는 대로 코드를 작성했다.

N, M = map(int, input().split())
dictN = []
result = []

for _ in range(N):
    dictN.append(input())

for _ in range(M):
    x = input()
    if x in dictN:
        result.append(x)
result.sort()
print(len(result))
for y in result:
    print(y)

 

dictN에 '듣도 못한 사람'의 리스트를 저장하고

해당 리스트에 없는 '보도 못한 사람'을 result에 저장하면서 result 자체가 '듣도 보도 못한 사람'이 되도록 했다.

 

그런데 이렇게만 했더니 시간초과가 떴다.

 

트러블 슈팅: 해시테이블과 시간 복잡도

---

리스트는 in연산 시 앞에서부터 차례로 하나씩 비교한다.

즉, 최악의 경우 N개를 전부 다 봐야 하고 시간복잡도는 O(N)이 된다.

 

해시 테이블(Hash Table)

해시 테이블은 키(key)를 빠르게 찾기 위해 해시 함수(hash function)를 이용해서 배열의 특정 위치(index)에 바로 접근하는 구조이다.

my_set = {'apple', 'banana', 'cherry'}

1. 'banana'를 저장할 때:
   • 'banana' → 해시 함수 → 숫자 (예: 839482)
   • 이 숫자를 배열의 인덱스로 변환 (보통 모듈러 연산 사용: % 배열크기)
   • 해당 인덱스 위치에 'banana' 저장
2. 'banana' in my_set:
   • 같은 방식으로 해시 계산 → 바로 해당 위치 조회
   • 다른 값을 다 볼 필요가 없음!

파이썬 해시 테이블 종류

자료구조	키	값	저장 방식
dict	O	O	키: 해시 → 값 저장
set	O	X	값 자체를 키처럼 저장

• dict는 키-값 쌍 저장
• set은 값을 키처럼 저장 (값만 있음)
• 둘 다 내부적으로 해시 테이블을 사용

딕셔너리(dict)가 해시 테이블인 건 알았는데 set도 해시 테이블로 동작한다는 걸 이번 문제를 통해 알게됐다.

 

두 개의 서로 다른 키가 같은 해시값을 가질 수도 있다.

이를 해시 충돌(Collision)이라고 하는데, 파이썬은 보통 체이닝(Chaining)방식으로 해결한다.

• 같은 위치에 여러 값을 연결 리스트처럼 저장
• 충돌이 많지 않으면 탐색은 거의 O(1) 수준을 유지함

결론

 

• 리스트는 선형 탐색 → O(N)
• 딕셔너리(dictionart)와 셋(set)은 해시 함수로 → 바로 위치 계산 → 평균 O(1)
• 파이썬의 해시 테이블은 충돌 관리, 리사이징 등도 자동으로 처리

N, M = map(int, input().split())
dictN = set()
result = []

for _ in range(N):
    dictN.add(input())

for _ in range(M):
    key = input()
    if key in dictN:
        result.append(key)

result.sort()
print(len(result))
for y in result:
    print(y)

set()으로만 바꿔줬는데 통과됐다.

 

in 연산자를 통해 값의 유무를 결정할 때는 리스트보다 해시테이블 자료구조를 사용하자!