문제 설명
영어 사전을 나타내는 단어 리스트가 주어졌을 때, 리스트의 다른 단어들을 한 글자씩 차례로 이어 붙여 만들 수 있는 가장 긴 단어를 찾는 문제입니다. 만약 답이 여러 개라면 그중 사전순(lexicographical order)으로 가장 앞선 단어를 반환하고, 조건을 만족하는 단어가 없다면 빈 문자열("")을 반환합니다.
예를 들어 입력이 ["h", "he", "hel", "hell", "hello"]라면, 각 단어가 바로 앞 단어에 한 글자씩 추가된 형태이므로 출력은 "hello"가 됩니다.
접근 방법: 트라이(Trie) 자료구조 활용
이 문제는 문자열 저장에 최적화된 트리 구조인 트라이(Trie)를 사용하면 효율적으로 해결할 수 있습니다. 전체 알고리즘은 다음과 같습니다.
- insert(word): 모든 단어를 트라이에 삽입합니다. 단어의 마지막 문자 노드에 끝 표시('#')를 남겨 완성된 단어를 구분합니다.
- search(word): 단어를 구성하는 모든 접두사가 사전에 등록된 완성된 단어인지 확인합니다. 탐색 중간에 끝 표시가 없는 노드가 나오면 False를 반환합니다.
- 모든 단어를 검사하며, 검색에 통과한 단어 중 길이가 가장 길거나, 길이가 같다면 사전순으로 더 앞선 단어를 정답으로 갱신합니다.
구현 코드
class Solution:
def longestWord(self, words):
self.trie = {}
def insert(word):
now = self.trie
for c in word:
if c not in now:
now[c] = {}
now = now[c]
now['#'] = True # 단어의 끝 표시
def search(word):
now = self.trie
for c in word:
now = now[c]
if '#' not in now: # 중간 접두사가 완성된 단어가 아니면 실패
return False
return True
for word in words:
insert(word)
ans = ""
for word in words:
if search(word) and (len(word) > len(ans) or (len(word) == len(ans) and word < ans)):
ans = word
return ans
ob = Solution()
print(ob.longestWord(["h", "he", "hel", "hell", "hello"]))
입력
["h", "he", "hel", "hell", "hello"]
출력
hello
동작 원리와 복잡도 분석
트라이는 문자열을 문자 하나씩 노드로 연결해 저장하는 구조입니다. "hello"를 검색할 때 루트에서부터 h → he → hel → hell 경로상의 모든 노드에 끝 표시('#')가 있는지 확인하므로, 해당 단어가 이전 단어들로부터 한 글자씩 만들어질 수 있는지 자연스럽게 판별할 수 있습니다.
단어의 개수를 N, 평균 길이를 L이라고 하면, 삽입과 검색에 각각 O(N × L)의 시간이 소요되므로 전체 시간 복잡도는 O(N × L)입니다. 공간 복잡도 역시 트라이 저장을 위해 O(N × L)이 필요합니다. 정렬 기반의 단순 비교 방식보다 접두사 검증이 빠르다는 점이 이 접근법의 가장 큰 장점입니다.