자바 Trie(트라이) 자료구조로 자동완성과 접두어 검색 구현하기

검색창 자동완성이나 사전 조회 기능을 만들다 보면 접두어로 후보를 빠르게 찾아야 하는 순간이 온다. 그럴 때 매번 문자열 목록 전체를 startsWith로 훑으면 데이터가 늘수록 느려진다. 이 문제를 자료구조로 푸는 표준 답이 Trie다. 코딩테스트에서도 LeetCode 208번을 비롯해 단골로 나온다.

결론부터 말하면, Trie는 접두어를 트리 경로로 표현해 insert, search, startsWith를 문자열 길이 L에 비례하는 O(L)로 처리하는 자료구조다. 자식 노드는 문자 집합이 작고 고정이면 배열, 크거나 희소하면 HashMap으로 저장한다. 코딩테스트에서 시간초과보다 메모리초과로 더 자주 넘어지므로 노드 개수를 의식하며 구현하는 게 핵심이다.

1. Trie가 무엇이고 왜 쓰는가

Trie(트라이, 접두어 트리라고도 한다)는 문자열을 문자 단위로 쪼개 트리 경로로 저장하는 자료구조다. 루트에서 시작해 한 글자씩 자식 노드를 따라 내려가고, 단어가 끝나는 노드에 "여기서 단어 하나가 끝난다"는 표시를 남긴다.

예를 들어 app과 apple을 넣으면 a-p-p 경로를 공유하고 그 뒤로 l-e가 이어진다. 접두어를 공유하는 단어끼리 경로를 나눠 쓰기 때문에, "app로 시작하는 단어가 있나?"를 세 글자만 따라가면 바로 판정할 수 있다.

핵심 항목만 압축하면 이렇다.

• 목적: 접두어 검색, 자동완성, 사전 조회를 빠르게.
• 구성: 각 노드는 자식 노드들과 단어 종료 표시(isEnd)를 가진다.
• 장점: 검색이 문자열 길이 L에만 비례한다. 저장된 단어 개수 N과 무관하게 O(L).
• 단점: 노드마다 자식 저장 공간을 두므로 메모리를 많이 먹는다.

2. 노드 정의 - 배열이냐 HashMap이냐

Trie 구현에서 가장 먼저 정하는 게 자식 노드를 어떻게 담을지다. LeetCode 208번은 입력이 소문자 알파벳 26개로 제한된다(word, prefix 길이 1~2000, 소문자 영어만). 이렇게 문자 집합이 작고 고정이면 크기 26짜리 배열이 깔끔하다.

// 배열 버전: children[0]='a' ... children[25]='z'
class Trie {
    private static final int R = 26;
    private final Trie[] children = new Trie[R];
    private boolean isEnd;
}

children[c]가 null이면 그 글자로 이어지는 경로가 없다는 뜻이다. 인덱스는 char - 'a'로 계산한다.

3. insert / search / startsWith 구현

세 메서드의 정의부터 한 줄로 끊어 둔다.

• insert(word): 단어를 한 글자씩 내려가며 없는 노드는 만들고, 마지막 노드에 isEnd = true를 찍는다.
• search(word): 경로를 끝까지 따라간 뒤 그 노드가 단어 종료 노드인지까지 확인한다.
• startsWith(prefix): 경로만 존재하면 참. 종료 여부는 보지 않는다.

search와 startsWith는 경로 추적이 똑같고 마지막 판정만 다르다. 그래서 공통 탐색 함수 find를 하나 두고 재사용한다.

class Trie {
    private static final int R = 26;
    private final Trie[] children = new Trie[R];
    private boolean isEnd;

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.children[c] == null) {
                node.children[c] = new Trie();
            }
            node = node.children[c];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = find(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private Trie find(String s) {
        Trie node = this;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if (node.children[c] == null) return null;
            node = node.children[c];
        }
        return node;
    }
}

여기서 한 번 잘 걸린다. search에서 node.isEnd 검사를 빼먹으면 startsWith와 똑같이 동작한다. 그러면 app만 넣었을 때 search("ap")가 true로 나온다. 경로가 있는 것과 단어가 저장된 것은 다르다는 점을 isEnd로 구분한다.

4. 실행 결과

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));    // 저장됨
        System.out.println(trie.search("app"));       // 경로만 있고 단어 아님
        System.out.println(trie.startsWith("app"));   // 접두어 존재
        trie.insert("app");
        System.out.println(trie.search("app"));       // 이제 단어
    }
}

true
false
true
true

search("app")가 처음엔 false, app을 넣은 뒤엔 true로 바뀌는 게 isEnd가 하는 일이다.

5. HashMap 버전

문자 집합이 넓거나(대소문자, 숫자, 유니코드) 자식이 드문드문 차는 경우엔 배열이 낭비다. 그럴 때는 자식을 HashMap으로 담아 실제 존재하는 글자만 저장한다.

import java.util.HashMap;
import java.util.Map;

class Trie {
    private final Map<Character, Trie> children = new HashMap<>();
    private boolean isEnd;

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            node = node.children.computeIfAbsent(c, k -> new Trie());
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = find(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private Trie find(String s) {
        Trie node = this;
        for (int i = 0; i < s.length(); i++) {
            Trie next = node.children.get(s.charAt(i));
            if (next == null) return null;
            node = next;
        }
        return node;
    }
}

computeIfAbsent로 없는 자식만 새로 만든다. 문자를 인덱스로 변환할 필요가 없어 유니코드든 무엇이든 그대로 넣을 수 있다.

6. 코딩테스트에서 자주 틀리는 메모리초과

Trie는 시간복잡도로 잘 안 막힌다. 대신 메모리에서 넘어진다. 이유를 짚어 본다.

배열 폭발. 배열 버전은 노드마다 크기 R짜리 참조 배열을 항상 들고 있다. R이 26이면 노드 하나가 참조 26개에 배열 객체 오버헤드까지 얹는다. 노드 개수는 최악의 경우 저장한 모든 단어의 글자 수 합에 근접한다. 단어가 많고 접두어를 잘 공유하지 않으면 노드가 수십만 개로 불어나 메모리가 터진다.

문자 집합을 크게 잡은 실수. 소문자만 필요한데 습관적으로 new Trie[128](아스키 전체)이나 그 이상으로 잡으면 노드마다 낭비하는 참조가 배로 늘어난다. 문제에서 허용 문자를 확인하고 딱 그만큼만 잡는다. 소문자 영어만이면 26이다.

재귀 구현의 스택 깊이. insert나 find를 문자 인덱스로 재귀 호출하도록 짜면, 길이 2000짜리 입력에서 재귀 깊이가 2000까지 간다. 호출이 많이 겹치면 스택이 위험하다. 위 예제처럼 반복문으로 짜면 이 문제가 없다.

노드 수를 대략 잡아 보려면 이렇게 센다. 환경에 따라 다르지만, 배열 버전 노드 하나는 64비트 JVM에서 대략 수십에서 100바이트 남짓을 쓴다고 보고, 단어 총 글자 수 x 노드당 바이트가 메모리 한계에 근접하는지 어림하면 된다.

7. 배열 vs HashMap, 무엇을 쓸까

정리하면 선택 기준은 문자 집합의 크기와 밀도다.

• 배열을 쓴다: 문자 집합이 작고 고정(소문자 26개 등)이며 노드가 조밀하게 찰 때. 인덱스 접근이라 상수 시간이 빠르고 해시 계산 오버헤드가 없다. LeetCode 208처럼 "lowercase English letters"가 명시된 문제는 배열 26이 정답에 가깝다.
• HashMap을 쓴다: 문자 집합이 크거나(대소문자+숫자=62, 유니코드) 자식이 희소할 때. 실제 존재하는 자식만 저장하므로 메모리를 아낀다. 대신 노드마다 HashMap 객체 오버헤드가 붙고, 해시 계산 비용이 상수에 얹힌다.

즉 작고 빽빽하면 배열, 크고 성기면 HashMap이다. 코딩테스트에서 소문자 제약이 걸려 있으면 고민 없이 배열 26으로 가는 게 빠르고 안전하다. 실무 자동완성처럼 한글이나 다국어를 다뤄야 하면 HashMap 쪽이 현실적이다.

8. 마무리

Trie의 뼈대는 세 가지다. 노드에 자식 저장소와 isEnd를 두고, 세 메서드는 경로를 따라 내려가는 같은 로직을 공유하되 search만 종료 여부를 추가로 본다. 여기까지는 배열이든 HashMap이든 동일하다. 갈리는 지점은 자식 저장 방식 하나이고, 그 선택이 곧 메모리와 속도의 트레이드오프다. 문자 집합을 먼저 확인하고 저장소를 고르는 습관만 들이면 메모리초과로 미끄러질 일이 크게 줄어든다.