Trie

• Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있다
• 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다
• DFS 형태로 검색을 해보면 사전 순서대로 단어를 탐색할 수 있다 (be, bee, can, cat, cd)
  

사용 목적

• 사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있다
• 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다.
• 단, 빠르게 탐색이 가능하다는 장점이 있지만 저장 공간의 크기가 크다는 단점도 있다
• 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다

시간 복잡도

• 제일 긴 문자열의 길이를 L 총 문자열들의 수를 M이라 가정하자
• 생성시 시간복잡도: O(M*L), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(M*L)만큼 걸린다. 물론 삽입 자체만은 O(L)만큼 걸린다
• 탐색시 시간복잡도: O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸린다

기본 문제

문제

n개의 수열이 주어집니다.
임의의 수열 a가 다른 어떠한 수열 b의 접두사가 되는지 판단하는 프로그램을 작성해보세요. 단, 이 문제에서는 정확히 일치하는 두 수열에 대해서는 접두사라 판단하지 않음에 유의합니다.

입력

첫 번째 줄에는 수열의 수 n이 주어집니다.
두 번째 줄부터 n개의 줄에 걸쳐 각 줄에 하나의 수열이 주어집니다. 수열은 전부 숫자로만 이루어져 있습니다.

• 1 ≤ n ≤ 10,000
• 1 ≤ 수열의 길이 ≤ 10

출력

임의의 수열 a가 다른 어떠한 수열 b의 접두사가 된다면 0을, 그러한 것이 없다면 1을 출력합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static class Node{
        Node[] children = new Node[10];
        boolean isEnd;
        public Node(){
            isEnd = false;
            for(int i = 0; i < 10; ++i){
                children[i] = null;
            }
        }
    }
    static Node root = new Node();
    static int n;
    static String text;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; ++i){
            text = br.readLine();
            if(insertText(text) == 0) {
                System.out.println(0);
                System.exit(0);
            }
        }
        System.out.println(1);
        br.close();
    }

    static int insertText(String text){
        Node node = root;
        for(int i = 0; i < text.length(); i++){
            if(node.isEnd) return 0;
            if(node.children[text.charAt(i) - '0'] == null){
                node.children[text.charAt(i) - '0'] = new Node();
            }
            node = node.children[text.charAt(i) - '0'];
        }
        node.isEnd = true;
        return 1;
    }
}

백준 14725 개미굴

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 *  시간 : 100ms, 메모리 : 13,680KB
 */
public class 개미굴 {
    static class Node {
        TreeMap<String, Node> children = new TreeMap<>();
    }

    static Node root = new Node();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int k = Integer.parseInt(input[0]);
            String[] texts = Arrays.copyOfRange(input, 1, k + 1);
            insertText(texts);
        }

        printTrie(root, 0);
        System.out.println(sb);
    }

    static void insertText(String[] texts) {
        Node node = root;
        for (String text : texts) {
            node.children.putIfAbsent(text, new Node());
            node = node.children.get(text);
        }
    }

    static void printTrie(Node node, int depth) {
        for (String key : node.children.keySet()) {
            for (int i = 0; i < depth; i++) {
                sb.append("--");
            }
            sb.append(key).append("\n");
            printTrie(node.children.get(key), depth + 1);
        }
    }
}

백준 7432 디스크 트리

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;

/**
 *  시간 : 188ms, 메모리 : 26,444KB  
 */
public class 디스크_트리 {
    static class Node{
        TreeMap<String, Node> children = new TreeMap<>();
    }
    static Node root = new Node();
    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; ++i){
            String[] texts = br.readLine().split("\\\\");
            insertText(texts);
        }
        printTrie(root, 0);
        System.out.print(sb);
        br.close();
    }

    static void insertText(String[] texts){
        Node node = root;
        for (String text : texts) {
            node.children.putIfAbsent(text, new Node());
            node = node.children.get(text);
        }
    }
    
    static void printTrie(Node node, int depth){
        for (String key : node.children.keySet()) {
            for (int i = 0; i < depth; i++) {
                sb.append(" ");
            }
            sb.append(key).append("\n");
            printTrie(node.children.get(key), depth + 1);
        }
    }
}