카카오 2026 상반기 코테에서 문자열 문제가 쏟아졌다는 후기가 커뮤니티에 올라왔다. 문자열 하면 보통 KMP나 해싱부터 떠올리는데, 의외로 트라이(Trie)가 정답인 경우가 꽤 있다. 오늘은 트라이를 "언제" 꺼내야 하는지, 그 감각에 대해 얘기해보려 한다.

"접두사"라는 단서

문제를 읽다가 "접두사", "자동완성", "사전순으로 k번째" 같은 키워드가 눈에 들어오면 트라이를 의심해야 한다. 해시맵으로도 풀 수 있지 않냐고? 물론이다. 단어 존재 여부만 확인하는 거라면 해시셋이 훨씬 간단하다. 근데 "이 접두사로 시작하는 단어가 몇 개야?", "접두사를 공유하는 단어 중 사전순 첫 번째를 찾아라" 같은 질문이 붙으면 이야기가 완전히 달라진다.

해시맵으로 접두사 검색을 하려면 모든 단어를 순회하면서 startswith를 돌려야 한다. O(N×L). 트라이는 접두사 길이만큼만 타고 내려가면 되니까 O(L). 단어 수가 10만 개이고 접두사 쿼리도 10만 번이면, 이 차이가 TLE와 AC를 가른다. 감이 안 오면 숫자를 대입해 보자. N=100,000, L=10이면 해시맵은 10억 연산, 트라이는 100만 연산. 100배 차이다.

Python 최소 구현

트라이 구현이 복잡할 것 같지만, 핵심은 딕셔너리의 딕셔너리다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0  # 이 노드를 지나간 단어 수

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.count += 1

    def count_prefix(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.count

count 필드 하나 추가했을 뿐인데 "이 접두사로 시작하는 단어 수"를 O(L)에 뽑아낸다. 프로그래머스 Lv.4 '자동완성' 문제가 딱 이 패턴이다. 각 단어를 트라이에 넣고, 한 글자씩 내려가면서 count가 1이 되는 지점 — 그러니까 더 이상 다른 단어와 겹치지 않는 지점 — 까지의 길이를 세면 끝.

코테에서 만나는 세 가지 패턴

패턴 1: 접두사 존재/개수 확인

위 코드가 그대로 적용된다. "전화번호 목록"(프로그래머스 Lv.2)이 대표 문제. 한 번호가 다른 번호의 접두사인지 확인할 때, 정렬 후 인접 비교로도 풀리지만 트라이 풀이를 알아두면 "접두사인 쌍이 총 몇 개냐" 같은 변형에 즉시 대응할 수 있다.

패턴 2: 사전순 k번째 문자열

트라이의 각 노드에 서브트리 크기를 저장하면, 루트에서부터 "왼쪽 자식의 크기가 k 이상인가?"를 따져서 내려갈 수 있다. 이진 탐색 트리에서 k번째 원소 찾는 로직이랑 같은 아이디어다. 알파벳 순서대로 자식을 탐색하니까 사전순이 자동으로 보장된다는 게 트라이의 매력.

패턴 3: XOR 최댓값 (비트 트라이)

좀 의외인 유형인데, 정수 배열에서 두 수의 XOR이 최대인 쌍을 찾는 문제에 비트 트라이가 등장한다. 각 수를 이진수로 변환해서 최상위 비트부터 트라이에 넣고, 탐색할 때는 현재 비트와 반대되는 자식이 있으면 그쪽으로 가는 그리디 전략을 쓴다. XOR은 서로 다른 비트가 많을수록 값이 커지니까. 백준 13505번 "두 수 XOR"이 이 유형이고, Codeforces에서도 종종 나온다.

그러면 해시는 언제 쓰고, 트라이는 언제 쓰나

솔직히 대부분의 문자열 존재 확인 문제는 해시셋으로 충분하다. 트라이를 꺼내야 하는 신호는 세 가지로 좁힐 수 있다:

  • 접두사 기반 쿼리가 반복된다

  • 사전순 탐색이 필요하다

  • 비트 단위 최적화가 필요하다 (XOR 계열)

이 세 가지가 아니면 괜히 트라이 짜다가 코드만 길어지고 시간만 날린다. 면접에서 "왜 트라이를 선택했나요?"라고 물었을 때 "접두사 쿼리가 O(L)이니까요"라고 한 문장으로 답할 수 있어야 한다. 근거 없이 복잡한 자료구조를 꺼내면 오히려 감점이다.

Java에서는 배열이 낫다

class Trie {
    int[][] ch = new int[1_000_001][26];
    int[] cnt = new int[1_000_001];
    int idx = 0;

    void insert(String word) {
        int cur = 0;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (ch[cur][i] == 0) ch[cur][i] = ++idx;
            cur = ch[cur][i];
            cnt[cur]++;
        }
    }
}

HashMap 대신 2차원 배열을 미리 잡아두면 GC 부담이 없고 노드 접근도 O(1)이다. Python에서는 딕셔너리가 편하지만 Java·C++에서는 배열 기반 트라이가 속도 면에서 압도적이다. 시간 제한이 빡빡한 환경이라면 이 방식이 안전하다.

한 가지 주의할 점: 배열 크기를 넉넉히 잡아야 한다. 단어 수 × 평균 길이 정도로 1_000_001을 설정했는데, 문제 조건에 따라 조정이 필요하다. 메모리 제한이 256MB인 문제에서 26 × 1,000,001 × 4바이트 ≈ 100MB이니까 여유가 있는 편이지만, 알파벳 소문자만 쓰이는지 확인하는 습관은 들여야 한다.