글자를 가지처럼! 트라이

• 트라이가 어떻게 생겼는지 안다.
• 단어를 삽입한다.
• 접두사 검색과 완전 일치를 구분한다.
• 각 노드에 개수를 세어 접두사 통계를 낸다.
• 접두사 관계를 판별한다.

비유로 이해하기 — 사전의 색인

사전에서 "cat" 을 찾으려면 c 페이지로 가고, 그 안에서 ca, 다시 cat 으로 좁혀간다냥. car 도 ca 까지는 같은 길을 쓴다냥.

트라이는 이 "같은 앞부분은 같은 길" 을 그대로 나무로 만든 거라냥. cat 과 car 은 c → a 까지 한 길을 공유하고, 거기서 t 와 r 로 갈라진다냥.

setdefault(ch, {}) 는 "ch 가 있으면 그걸 주고, 없으면 빈 딕셔너리를 넣고 그걸 준다냥." 트라이 삽입에 딱 맞는 도구라냥.

끝 표시를 확인 안 하면 접두사를 단어로 착각한다냥.

사전에 "apple" 만 있는데 "appl" 을 물으면, 글자는 다 따라가진다냥. 하지만 "appl" 자리에는 끝 표시가 없다냥. 끝 표시를 안 보면 "있다" 고 잘못 답한다냥.

오늘 1번(접두사 개수)과 2번(완전 일치)이 바로 이 차이라냥. 같은 트라이인데 끝 표시를 보느냐 마느냐로 갈린다냥.

"서로 다른 접두사가 모두 몇 개냥?" 은 곧 트라이의 노드 수(루트 제외) 라냥. 삽입 중 새 노드를 만들 때마다 세면 된다냥. 오늘 4번 문제라냥.

삽입하면서 두 가지를 본다냥.

단어 w 를 트라이에 넣는 도중에 —

• 끝 표시를 지나치면 → 더 짧은 단어가 w 의 접두사라냥
• 다 넣은 노드에 이미 자식이 있으면 → w 가 더 긴 단어의 접두사라냥

둘 중 하나라도 걸리면 접두사 관계가 있는 거라냥.

node = root
for ch in w:
    if "$" in node:            # 더 짧은 단어가 여기서 끝났다냥
        conflict = True
    node = node.setdefault(ch, {})
if len(node) > 0:              # 내 끝에 이미 자식이 있다냥
    conflict = True
node["$"] = True

넣는 순서에 상관없이 이 두 검사를 매 단어마다 하면 접두사 관계를 놓치지 않는다냥. 짧은 걸 먼저 넣든 긴 걸 먼저 넣든, 둘 중 한 검사에 걸린다냥. 오늘 3번 문제라냥.