13. 문자열-Trie

문자열 - Trie

Summary

접두사 검색, 자동완성, 사전 단어 존재 확인에서 Trie를 의심한다.
카카오/네이버/라인류 문자열 변형에서 가끔 나온다.

---

Trie 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    static class TrieNode {
        Map<Character, TrieNode> child = new HashMap<>();
        boolean end;
    }
 
    static class Trie {
        TrieNode root = new TrieNode();
 
        void insert(String word) {
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                cur = cur.child.computeIfAbsent(c, k -> new TrieNode());
            }
            cur.end = true;
        }
 
        boolean search(String word) {
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                cur = cur.child.get(c);
                if (cur == null) return false;
            }
            return cur.end;
        }
 
        boolean startsWith(String prefix) {
            TrieNode cur = root;
            for (char c : prefix.toCharArray()) {
                cur = cur.child.get(c);
                if (cur == null) return false;
            }
            return true;
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Trie trie = new Trie();
 
        for (int i = 0; i < n; i++) {
            trie.insert(br.readLine());
        }
 
        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            String s = br.readLine();
            sb.append(trie.search(s) ? "YES" : "NO").append(' ');
            sb.append(trie.startsWith(s) ? "PREFIX" : "NO_PREFIX").append('\n');
        }
 
        System.out.print(sb);
    }
}

---

문제 신호

접두사
자동완성
사전 검색
문자열 집합에서 빠른 존재 확인
공통 prefix

---

주의점

실수	주의
end 표시 누락	prefix와 완전한 단어 구분 불가
알파벳 범위 고정 착각	소문자만인지 전체 문자인지 확인
메모리 과다	문자 종류가 작으면 배열, 크면 HashMap
정렬 문제와 혼동	prefix만 필요하면 Trie가 더 직접적

---

백지 복원

1. TrieNode에 반드시 필요한 두 필드는?
2. search와 startsWith의 차이는?
3. end 표시가 없으면 어떤 문제가 생기는가?