[백준 2179] 비슷한 단어

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

알고리즘 : 해시

난이도 : 골드Ⅳ

 

1. 문제요약

• N개의 영단어가 주어진다. N은 20000이하의 자연수이고 각 영단어는 소문자로 이루어진 100자이내의 단어이다.
• 두 단어를 앞글자부터 확인하여 공통되는 부분의 길이가 길어질 수록 두 단어가 비슷한 정도가 커진다고 하자. 예를들어 abcd와 abecd가 있을때 두 단어를 앞에서부터 보면 ab가 공통된다.
• N개의 단어에서 가장 비슷한 단어를 출력한다. 단 비슷한 단어가 여러개인 경우 입력이 빠른 순대로 출력한다. 예시입출력은 아래와 같다.

2. 아이디어

• 단어를 한쌍씩 일일히 비교하면 $O(N^2)$의 시간복잡도를 갖게되어 단어가 2만개가 주어진다면 시간초과가 된다.
• 시간복잡도 충족을 위해 모든 단어를 앞에서부터 한글자씩 늘어나는 형태로 슬라이싱하여 각 단어가 key가 되도록 딕셔너리에 저장하는 방법을 생각해 볼 수 있다. 예를들어 길이가 6인 단어인 memory는 m, me, mem, memo, memor, memory 총 6개의 단어로 슬라이싱하여 딕셔너리에 각각 저장하는 것이다.
• 단어의 길이가 100글자 이내이므로, 2만개의 단어가 주어진다 하더라도 200만번 정도의 연산으로 위와 같은 형태로 입력값들을 저장할 수 있다.
• 이렇게 슬라이싱 된 단어를 딕셔너리에 value 1로 저장시키고, 이후 동일한 단어가 나올때마다 value를 1씩 증가시키면 모든 공통된 단어를 확인할 수 있고, 딕셔너리의 탐색속도가 $O(1)$에 불과하므로 시간복잡도도 충족할 수 있게 된다.

3. 느낀점

• 문제를 보고 아이디어를 떠올리기까지 시간이 좀 걸린 문제였다. 코딩테스트같은 긴장되는 상황이었다면 시간내에 풀수 있었을지 모르겠다.
• 시간효율을 만족시키기 위해 메모리효율을 희생시키는 아이디어를 적용했어야 한다는 점에서 해시라는 자료구조의 특성을 느낄 수 있는 좋은 문제였다고 생각한다.

4. 파이썬 코드

import sys
input = lambda:sys.stdin.readline().rstrip()

n = int(input())
words = [input() for _ in range(n)]

# 길이 m의 단어를 길이 1 ~ 길이 m으로 잘라서 딕셔너리에 넣어 카운팅
check = dict()
for word in words:
    tmp = ''
    for ch in word:
        tmp += ch
        check[tmp] = check.get(tmp,0) + 1

# 가장 긴 접두사 shared와 그 길이 max_length 구하기
shared, max_length = '', 0
for a,b in check.items():
    tmp_length = len(a)
    if b > 1:
        if tmp_length > max_length:
            shared = a
            max_length = tmp_length

# 접두사 공유하는 가장 앞쪽의 단어 탐색
cnt = 0
for word in words:
    if shared == word[:max_length]:
        cnt += 1
        print(word)
    if cnt == 2:
        break