문제
접근
Trie 알고리즘을 사용했다.
Trie 알고리즘은 문자열 검색에 사용되는 알고리즘이다.
문자열을 트리형식으로 저장하여 빠르게 검색할 수 있다.
각 문자열을 단어 단위로 트리 형식으로 연결한다.
트리의 깊이가 단어의 길이가 되는 형식이다.
트리 노드의 기본 구조는 다음과 같다.
해당 노드의 key, 즉 알파벳
해당 노드의 데이터, 현재 노드까지 왔을 때 완성되는 단어(만약 없는 단어라면 None)
해당 노드의 자식 노드들, 딕셔너리 형식으로 상수시간에 검색하도록 한다.
해당 문제는 노드의 데이터(현재 노드까지 왔을 때 완성되는 단어의 모습)이 필요가 없다.
단지 현재 노드에 도달 했을 때 아래에 자식이 더 있는지 없는지만 확인하면 된다.
자식이 없다면 현재 노드까지만 입력하면 자동완성이 가능하고, 자식이 있다면 더 타고들어야 할 것이다.
이를 해결하기 위해 데이터 대신 카운팅을 넣어주고 노드에 방문할 때마다 해당 노드의 카운트를 하나씩 늘려주었다.
해당 노드의 카운트가 0인 경우는 존재할 수 없다.
0은 해당 노드가 만들어지지 않은 경우니까!
1인 경우는 해당 노드에 한 번만 방문했다는 의미이므로, 현재 단어 빼고는 해당 노드를 거치는 노드가 없다는 의미다.
따라서 현재 단어의 알파벳 위치까지만 입력해주면 자동완성이 가능해진다.
2 이상인 경우는 여러 단어가 이 노드를 거쳐간다는 의미이다.
따라서 아직 자동완성이 불가능하기 때문에 다음 노드로 탐색을 이어간다.
해당 단어를 끝까지 탐색했음에도 카운트가 1인 노드를 만나지 못했다면, 해당 단어는 다른 단어의 접두사라는 의미이다.
따라서 해당 단어는 단어의 전부를 입력해야 한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Node(object):
def __init__(self, key, cnt = 0):
self.key = key
self.cnt = cnt
self.child = {}
class Trie():
def __init__(self):
self.head = Node(None)
def insertTree(self, string):
cur = self.head
for token in string:
if token not in cur.child:
cur.child[token] = Node(token)
cur = cur.child[token]
cur.cnt += 1
def searchTree(self, string):
cur = self.head
cnt = 0
for token in string:
cnt += 1
cur = cur.child[token]
if cur.cnt == 1:
return cnt
return len(string)
def solution(words):
answer = 0
wordTree = Trie()
for word in words:
wordTree.insertTree(word)
for word in words:
answer += wordTree.searchTree(word)
return answer