🐹 비슷한 단어

1. 문제 링크

2469번: 비슷한 단어

2. 코드

Python3 34072kb 824ms

from collections import Counter

N = int(input())
words = []
max_prefix_len = 0  # 접두사의 최대 길이
for _ in range(N):
    word = input()
    max_prefix_len = max(max_prefix_len, len(word))
    words.append(word)

# M의 길이의 접두사 만들고 확인 
def check_prefix(M):
    prefix = []
    for w in words:
        prefix.append(w[:M])
    dict_prefix = Counter(prefix)
    
    result = []
    for key in dict_prefix.keys():
        if dict_prefix[key] > 1:
            result.append(key)
    return result

prefix = []
# 가장 긴 접두사 찾기
while max_prefix_len:
    prefix = check_prefix(max_prefix_len)
    if prefix:
        break
    max_prefix_len -= 1

idx = 0
# 접두사를 포함하는 가장 첫 단어 찾기(접두사도 찾기)
for i in range(len(words)):
    if words[i][:max_prefix_len] in prefix:
        prefix = words[i][:max_prefix_len]
        idx = i + 1
        print(words[i])
        break

# 확정된 접두사에 해당하는 두 번째 단어 찾기
for i in range(idx, len(words)):
    if words[i][:max_prefix_len] == prefix:
        print(words[i])
        break

3. 해설

단어의 개수가 최대 20000개 이므로 2개의 단어씩 짝을지어 각 알파벳을 확인하여 접두사를 찾는 3중 중첩문을 사용하면 시간초과가 나므로 다른 방법을 고민해봤다.

모든 단어를 공통적인 길이로 잘라 중복되는 단어가 있다면 그것이 겹치는 접두사가 될 것이고 해당 접두사의 길이가 가장 길도록 만들어주면 된다. 이를 위해 단어에서 가장 긴 단어를 접두사의 최대 길이로 두고 반복할 때마다 길이를 1씩 줄여가며 가장 긴 접두사의 길이를 찾는다.

check_prefix에서 입력된 접두사의 길이만큼 단어를 자른 후 딕셔너리로 만들어 접두사의 개수가 1이 넘게되는 접두사가 가장 긴 접두사가 된다. 이때 이를 만족하는 접두사가 여러 개 일 수 있으니 배열에 담아둔다.

접두사를 찾고 난 후 입력받은 순서대로 단어를 확인하고 접두사 배열에 포함된 접두사를 가진 단어를 찾고 출력한다. 이때 어떤 접두사를 사용할지 확정된다.(접두사 배열 속에서 입력 순서가 가장 단어에 포함된 접두사)

발견된 위치 다음부터 접두사가 포함된 가장 앞 순서 단어를 탐색하여 출력한다.