트라이(Trie)

정의

검색 트리의 일종
일반적으로 키가 문자열인 동적 배열 or 연관 배열을 저장하는 데 사용되는 정렬된 트리 구조
NLP(자연어 처리)분야에서 문자열 탐색을 위한 자료구조로 널리 사용됨

전형적인 다진 트리(M-ary Tree)의 형태
찾고자 하는 문자의 길이만큼만 탐색하면 됨

예시 문제

백준 14725

문제 핵심 : 단순히 다 출력하는 것이 아니라, 다진 트리를 만들어야 함
예제에는 함정이 없는데, 만약, input 값이

5
1 B
2 A A
3 A B A
3 A B K
4 A B C B

같은 경우, A-B를 공유하는 A, K, C-B는 같은 단으로 출력 되어야 함
출력 예시

A
--A
--B
----A
----C
------B
----K
B

정답 코드

N = int(input())
arr = []
for _ in range(N):
    ipt = input().split()
    arr.append(ipt[1::])
arr.sort()
for i in range(N):
    if not i:
        print(arr[i][0])
        for j in range(1, len(arr[i])):
            print('--'*j + arr[i][j])
    else:
        n = -1
        for j in range(len(arr[i])):
            if not arr[i-1][j] == arr[i][j]:
                n = j
                break
        for j in range(n, len(arr[i])):
            print('--' * j + arr[i][j])