Trie에 대해 알아보자

접두사 트리라고도 하는 Trie는 문자열을 효율적으로 검색하는 데 사용되는 트리 기반 데이터 구조입니다. Trie라는 이름은 영어로 "tree"로 발음되는 retrieval이라는 단어에서 유래되었습니다.

Trie 데이터 구조에서 각 노드는 접두사 또는 완전한 단어를 나타냅니다. 노드는 부모 노드가 모든 자식에 공통인 접두사를 나타내는 방식으로 연결됩니다. 각 자식 노드는 단어의 다음 문자를 나타냅니다. 리프 노드는 문자열의 끝을 나타냅니다.

다음은 Trie 데이터 구조의 예입니다.

     root
    /   \
   a     b
  / \     \
 n   r     y
/   / \     \

할 일
| |
ts

Trie에서 문자열을 검색하려면 루트 노드에서 시작하여 문자열의 문자에 해당하는 경로를 따릅니다. Trie에 경로가 존재하고 마지막 노드가 리프 노드이면 문자열이 Trie에 존재합니다.

Trie에 문자열을 삽입하려면 루트 노드에서 시작하여 문자열의 문자에 해당하는 경로를 따라갑니다. Trie에 경로가 있으면 마지막 노드를 리프 노드로 표시하기만 하면 됩니다. 경로가 Trie에 없으면 Trie에 새 노드를 추가하여 새 문자열을 나타냅니다.

다음은 Java에서 Trie 데이터 구조를 구현하는 방법의 예입니다.

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            TrieNode node = current.children.get(ch);
            if (node == null) {
                node = new TrieNode();
                current.children.put(ch, node);
            }
            current = node;
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            TrieNode node = current.children.get(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return current.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            TrieNode node = current.children.get(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return true;
    }
}

이 코드에서 'TrieNode'는 Trie의 각 노드를 나타내고 'Trie'는 Trie 데이터 구조를 나타냅니다. 'insert' 메서드는 Trie에 문자열을 삽입하고, 'search' 메서드는 Trie에서 문자열을 검색하며, 'startsWith' 메서드는 문자열이 Trie에 접두사로 존재하는지 확인합니다.

다음은 Java에서 Trie 데이터 구조를 사용하는 방법의 예입니다.

Trie trie = new Trie();
trie.insert("and");
trie.insert("ant");
trie.insert("any");
System.out.println(trie.search("and")); // output: true
System.out.println(trie.search("an")); // output: false
System.out.println(trie.startsWith("an")); // output: true

이 코드에서는 Trie 데이터 구조를 만들고 Trie에 세 개의 문자열을 삽입한 다음 Trie에서 검색 및 접두사 검색을 수행합니다. 검색 및 접두사 검색의 출력은 예상대로입니다.