트라이(Trie) 자료구조

💡 트라이(Trie)는 트리형태로 문자열을 저장해 빠르게 탐색하는 자료구조이다.

 

• 일반적인 이진트리의 시간 복잡도는 O(logN) 이지만, 길이가 M인 문자열을 저장하면 O(M*logN)의 시간 복잡도를 갖는 문제가 생긴다.
• 이러한 문제를 해결하기 위해서 Trie는 문자열의 문자 하나씩 노드에 저장한다.
• 문자열 하나를 검색할 때 O(N)의 시간 복잡도를 갖는다.
• Java에서는 Map 자료구조를 이용해 구현한다.

  

  https://codingnojam.tistory.com/40

• 저장된 문자열 : cap, code, kakao, kai

 

🚀 트라이 자료구조 생성 및 사용

• 검색하고자 하는 문자열을 트라이 클래스에 모두 저장한다.
  • 하나의 문자열을 저장할 때, 각 문자를 key로 자식 노드를 value로 트리 형태를 띄는지 확인한다.
  • 만약 현재 문자 key가 없다면, 생성해준다.
  • 마지막 노드에 boolean 값으로 true 표시한다.
• 검색할 때는 저장과 유사하게 문자 하나씩 검사한다.
  • key로 지정되지 않은 문자라면, 없는 문자열이므로 false를 반환한다.
  • 모든 문자가 있고, 마지막으로 나온 노드에 boolean이 true이면 해당 문자열이 저장되어 있다는 것이므로 true를 반환한다.

 

🚀 트라이 자료구조의 핵심코드

static class Node {
    // 자식노드
    Map<Character, Node> chiledNode = new HashMap<>();
    // 문자열의 마지막이면 true
    boolean isEnd;
}

static class Trie {
    // 루트노드
    Node rootNode = new Node();

    // Trie 문자열 저장
    void insert(char[] chars) {
        Node node = this.rootNode; // 루트 노드에서 시작

        // 문자열의 각 문자마다 자식노드에 있는지 체크
        // 없으면 자식노드 새로 생성
        for(char c : chars) {
            node = node.chiledNode.computeIfAbsent(c, key -> new Node());
        }
        // 저장 할 문자열의 마지막 단어에 매핑되는 노드에 단어의 끝임을 명시
        node.isEnd = true;
    }

    // Trie 문자열 검색
    boolean search(char[] chars) {
        Node node = this.rootNode; // 루트 노드에서 시작

        // 문자열의 각 문자마다 노드 존재하는지 체크 
        for(char[] chars : c) {
            // 매핑된 노드가 존재하면 가져오고, 없으면 null
            node = node.chiledNode.get(c);
            if(node == null) {
                return false; // 해당 문자열은 없음
            }
        }
        // 현재 노드가 마지막 문자여야 정확히 일치하는 문자열이 저장된 것
        return node.endOfword;
    }
}

 

• Node 클래스를 만들어 트리 구조를 생성한다.
• Trie 클래스의 insert() 메서드에서 문자에 해당하는 key가 없다면, 새로 노드를 만들어 저장한다.
• Trie 클래스의 search() 메서드에서 저장된 트리에 해당 문자열이 있는지 검색한다.

 

🚀 트라이 자료구조 예제  코드

백준 5052 전화번호 목록 문제 풀이 코드

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {

            int n = Integer.parseInt(br.readLine());
            Trie trie = new Trie();
            boolean isConsistent = true;

            for (int i = 0; i < n; i++) {
                if (!trie.insert(br.readLine().toCharArray()))
                    isConsistent = false;
            }
            if (isConsistent)
                sb.append("YES\n");
            else
                sb.append("NO\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private static class Trie { // 트라이 알고리즘

        private final Node rootNode = new Node(); // 루트 노드 싱글톤 생성

        public boolean insert(char[] chars) {
            Node node = rootNode; // 루트 노드부터 시작
            boolean isNewNodeCreated = false;

            for (char c : chars) { // 해당 key가 없으면 만들어 반환, 있으면 그 value를 반환
                if (!node.chiledNode.containsKey(c)) {
                    node.chiledNode.put(c, new Node());
                    isNewNodeCreated = true;
                }
                node = node.chiledNode.get(c);
                if (node.isEnd) { // 다른 번호가 이 번호의 접두어임
                    return false;
                }
            }

            if (!isNewNodeCreated) {
                return false; // 이 번호가 다른 번호의 접두어임
            }

            node.isEnd = true; // 문자열의 마지막이 되는 노드임
            return true;
        }
    }

    private static class Node {
        final Map<Character, Node> chiledNode;
        boolean isEnd;

        public Node() {
            this.chiledNode = new HashMap<>();
            this.isEnd = false;
        }
    }
}

 

🚀 참고

• https://codingnojam.tistory.com/40

 

🚀 관련 문제 풀이

• [G4] BOJ_5052 : 전화번호 목록 (24.05.19)