트라이(Trie) 자료구조 정리 (Java)

Trie

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

• "ant"를 추가하기 위하여 root의 자식노드 'a'가 존재하지 않으면 추가하고 동일한 방법으로 'n', 't' 추가

• "ant"를 탐색하기 위하여 root -> 'a' -> 'n' -> 't' 3번의 이동으로 탐색 가능

Java로 구현

• TrieNode

public class TrieNode {

    private Map<Character, TrieNode> childNodes = new HashMap<>();

    private boolean isLastChar;

    public Map<Character, TrieNode> getChildNodes() {
        return childNodes;
    }

    public boolean isLastChar() {
        return isLastChar;
    }

    public void setIsLastChar(boolean isLastChar) {
        this.isLastChar = isLastChar;
    }
}

• Trie

public class Trie {

    private TrieNode rootNode;

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

    void insert(String word) {
        TrieNode node = this.rootNode;

        for (int i = 0; i < word.length(); i++) {
            node = node.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
        }
        node.setIsLastChar(true);
    }

    boolean contains(String word) {
        TrieNode node = this.rootNode;

        for (int i = 0; i < word.length(); i++) {
            char charAtIdx = word.charAt(i);
            node = node.getChildNodes().get(charAtIdx);

            if (node == null) {
                return false;
            }
        }

        return node.isLastChar();
    }

    void delete(String word) {
        delete(this.rootNode, word, 0);
    }

    private void delete(TrieNode node, String word, int index) {
        char charAtIdx = word.charAt(index);
        TrieNode childNode = node.getChildNodes().get(charAtIdx);
        if(childNode == null) {
            System.out.println("There is no \"" + word + "\" in this Trie.");
            return;
        }

        index++;
        if (index == word.length()) {
            if (!childNode.isLastChar()) {
                System.out.println("There is no \"" + word + "\" in this Trie.");
                return;
            }

            if (!childNode.getChildNodes().isEmpty()) {
                childNode.setIsLastChar(false);
            } else {
                node.getChildNodes().remove(charAtIdx);
            }
        } else {
            delete(childNode, word, index);

            if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty()) {
                node.getChildNodes().remove(charAtIdx);
            }
        }
    }

    void print() {
        Queue<Map<Character, TrieNode>> queue = new LinkedList<>();
        queue.add(rootNode.getChildNodes());

        while (!queue.isEmpty()) {
            for (Map.Entry<Character, TrieNode> entry : queue.poll().entrySet()) {
                System.out.println(entry.getKey());
                queue.add(entry.getValue().getChildNodes());
            }
        }
    }
}

2020 카카오 코테 가사 검색 문제

• 문제는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 구하는 것
• 제한사항
  • '?'는 검색 키워드의 접두사 or 접미사 중 하나로만 주어짐
    • "??odf", "fro??", "?????" 는 가능한 키워드
    • "frodo", "fr?do", "?ro??" 는 불가능한 키워드
• 입출력 예시
  • words
    • ["frodo", "front", "frost", "frozen", "frame", "kakao"]
  • queries
    • ["fro??", "????o", "fr???", "fro???", "pro?"]
  • result
    • [3, 2, 4, 1, 0]
• 풀이
  • Trie를 사용하지만, "????o"와 같은 질문을 해결하기 위해 반대 Trie도 같이 생성
  • 예를들어 "frodo"의 경우 한 Trie는 "frodo"를, 다른 Trie는 "odorf"를 입력
  • TrieNode에 count를 추가하여 단어 입력 시 TrieNode를 지날 때마다 해당 TrieNode의 count를 1 증가 시킴
    • 질문과 매치되는 단어 수를 빠르게 구할 수 있음