백준에서 이 문제를 풀면서 알게 된 자료구조이다.
(그림 출처 : 위키백과)
트라이는 탐색 트리의 종류 중 하나인데, 그림처럼 자신을 하나 하나 때서 노드에 저장하고 맨마지막 노드까지 확인하면 비로소 어떤것인지 확인 할 수 있다.
이런 성질때문에 주로 알고리즘 문제를 풀때 ~이 ~안에 포함되는지 이런문제에서 주로 많이 사용한다.
무작정 문자열 비교를 한다면 최대길이가 m이고 문자열 n개라고 할때 O(mn)이 필요하지만,
트라이는 O(m) 이기때문에 훨씬 빠른다.
생성 시에는 O(mn)이 소모된다.
단점이 있다면 메모리초과 나는경우가 많다.
class Node():
def __init__(self,key):
self.key=key
self.children=dict()
class Trie():
def __init__(self):
self.head = Node(None)
def insert(self,string):
cNode=self.head
for c in string:
if c not in cNode.children :
cNode.children[c] = Node(c)
cNode=cNode.children[c]이게 가장 기초가 되는 코드이다.
Node는 자기자신의 값을 key에 가지고, 자식노드들을 딕셔너리로 저장한다.
트라이에서 맨 위 노드는 주로 쓰지 않으므로 생성자에서는 Node(None)으로 생성한다.
insert 함수에서는 cNode는 현재 가리키는 노드를 의미하는데, 함수가 처음시작되는 순간에는 None에 해당되는 노드가 될것이다.
이후 for문을 통해 자신의 글자를 집어넣는데,
if c not in cNode.children : cNode.children[c] = Node(c)
이 부분은 '만약 cNode.children(부모노드의 자식 딕셔너리)에 c 에 해당하는 노드가 없으면 {c:Node(c)}를 삽입한다는 의미이다.
예를 들어, 트라이에 'ten'이가 먼저 삽입되어있고, 'ted'를 삽입 할 차례라고 하면,
t나e는 이미 'ten'을 삽입할때 만들어져 있으므로 지나가면 되지만,
d를 삽입할때는 cNode가 Node(e)인 상태인데, Node(e).children은 {n:Node(n)} 인 상태이므로 d를 딕셔너리에 추가하여 최종적으로는 Node(e).children은 {n:Node(n),d:Node(d)} 가 된다.
insert함수를 이해했다면 문제에 따라서 필요한 탐색함수는 그때그때 만들어서 사용할 수 있을것이다.
문제에 따라서 마지막 노드를 표시할 필요가 있는문제가 있고, 없는문제가 있는데, 표시해야된다면 삽입할때 굳이 문자열이 rstrip()된 상태로 넣지않고, 일부러 '\n'을 넣어 마지막 노드임을 표시하는것도 좋은 아이디어 였다.
