[Java] 208. Implement Trie (Prefix Tree)

문제 파악

Trie 자료구조를 구현해야하는 문제이다.

 

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.

해시 테이블을 사용하면 되는데, 왜 트라이를 사용해야할까?

🚨 해시 테이블의 경우 접두사나 부분 문자열로 검색하기 힘들다. 또한, 해시 코드로 저장하기 때문에 정렬되어 있지 않다.

 

---

풀이

1️⃣ 

Node 클래스 정의

class Trie {
    
    Node root;

    static class Node {
        Map<Character, Node> children;
        boolean isEndOfWord;

        public Node() {
            this.children = new HashMap<>();
            this.isEndOfWord = false;
        }
    }

    public Trie() {
        this.root = new Node();
    }

}

 

Trie 자료구조는 트리 형태이기 때문에, 노드와 노드간의 연결로 표현해야한다.

 

따라서, Node 클래스를 정의해준다.

 

 

insert 구현

    public void insert(String word) {
        insert(this.root, word);
    }

    private void insert(Node node, String word) {
        if (word.length() == 0) {
            node.isEndOfWord = true;
            return;
        }

        char c = word.charAt(0);
        Node child;
        if (!node.children.containsKey(c)) {
            child = new Node();
            node.children.put(c, child);
        } else {
            child = node.children.get(c);
        }

        insert(child, word.substring(1));
    }

입력하는 문자열을 문자로 쪼개어 관리한다.

 

더이상 문자열이 없을 때까지 재귀적으로 동작하고, 문자열이 존재하지 않는 경우 isEndOfWord 필드를 true로 설정하고 빠져나온다.

 

 

search 구현

    public boolean search(String word) {
        return search(this.root, word);
    }

    private boolean search(Node node, String word) {
        if (word.length() == 0) {
            return node.isEndOfWord;
        }

        char c = word.charAt(0);
        if (!node.children.containsKey(c)) {
            return false;
        }
        
        return search(node.children.get(c), word.substring(1));
    }

insert 와 비슷하다.

 

문자열을 문자로 쪼갠 후, 각 문자에 해당하는 키 값으로하는 노드를 찾아간다.

 

만약, 키 값으로 하는 노드가 null 인경우 false를 반환한다.

 

startsWith 구현

    public boolean startsWith(String prefix) {
        Node currentNode = this.root;
        for (char c : prefix.toCharArray()) {
            if (!currentNode.children.containsKey(c)) {
                return false;
            }
            currentNode = currentNode.children.get(c);
        }

        return true;
    }

 

검색하려는 접두어를 문자로 쪼갠 뒤, 자식 노드가 해당 문자를 키값으로 하는 노드를 갖는지 검사하는 과정이다.

 

 

 

결과

 

---

📖 회고

Trie 라는 자료구조가 있다는 것을 강의를 통해 처음 알게 되었었는데

 

이렇게 바로 자료구조로서 구현하는 문제를 직접 풀어보니, Trie 자료구조에 대해 더 깊은 이해를 할 수 있었던 것 같다.

 

한번 해봤다고 끝낼 것이 아니라, 이 문제를 여러번 풀어봐야겠다는 생각이 들었다.