HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
[New] 타일러팀
[New] 타일러팀/
♠️
[자료구조] Trie
♠️

[자료구조] Trie

Category
Java
Created
Apr 30, 2022 07:32 PM
Person
State
완료

Trie

  • 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조
      • notion image
  • "ant"를 추가하기 위하여 root의 자식노드 'a'가 존재하지 않으면 추가하고 동일한 방법으로 'n', 't' 추가
  • "ant"를 탐색하기 위하여 root -> 'a' -> 'n' -> 't' 3번의 이동으로 탐색 가능
 

Java로 구현

  • TrieNode
  • Trie
 

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

코딩테스트 연습 - 가사 검색
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다.
코딩테스트 연습 - 가사 검색
https://programmers.co.kr/learn/courses/30/lessons/60060
코딩테스트 연습 - 가사 검색
  • 문제는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 구하는 것
  • 제한사항
    • '?'는 검색 키워드의 접두사 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 증가 시킴
      • 질문과 매치되는 단어 수를 빠르게 구할 수 있음
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;
    }
}

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());
            }
        }
    }
}