트라이(Trie)

: 문자열에서 검색을 빠르게 도와주는 자료구조

정수형에서 이진탐색트리를 이용하면 시간복잡도 O(logN)
하지만 문자열에서 적용했을 때, 문자열 최대 길이가 M이면 O(M*logN)이 된다.
트라이를 활용하면? → O(M)으로 문자열 검색이 가능함!

DFS 형태로 검색 시 : to, tea, ted, ten, A, i , in, inn

사용 목적

1. 문자열 탐색 시 시간복잡도 줄이기 위해

   → 빠르게 탐색이 가능하지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있어 메모리를 많이 차지함

2. 검색어 자동 완성, 사전에서 찾기, 문자열 검사

시간 복잡도

제일 긴 문자열 길이 L, 총 문자열 수 M

• 생성 시 : O(ML) : 모든 문자열을 넣어야 하니 M개에 대해서 트라이 자료구조에 넣는 건 가장 긴 문자열 만큼(L) 걸리니 O(ML) / 삽입 자체는 O(L)
• 탐색 시 : O(L) : 트리를 타고 들어가봐야 가장 긴 문자열만큼이 최대이므로

예제(백준 5052-전화번호 목록)

문제

이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

풀이

import sys
import math

class Node:
    def __init__(self, data):
        self.data = data
        self.child = [None for _ in range(10)]
        self.check = False #해당 노드를 마지막으로 끝나는 문자열이 있는지

class Trie:
    def __init__(self):
        self.root = Node('')

    def insert(self, phone):
        tmp = self.root
        for i in phone:
            if tmp.child[i] != None:  # 비어있지 않으면
                tmp = tmp.child[i]
            else:
                new = Node(i)
                tmp.child[i] = new
                tmp = new
        tmp.check = True

    def consistency(self, phone):
        tmp = self.root
        for i in range(len(phone)):
            if tmp.check:  # 다른 문자열을 포함하고 있다면
                return False
            tmp = tmp.child[phone[i]]
        return True

for _ in range(int(input())):
    n = int(input())
    phone_list = []
    trie = Trie()

    for _ in range(n):
        phone = list(map(int, input().split()))
        trie.insert(phone)
        phone_list.append(phone)
    result = True

    for p in phone_list:
        result *= trie.consistency(p)

    if result:
        print("YES")
    else:
        print("NO")