문제 보기 · Level 4 · 2018 KAKAO BLIND RECRUITMENT · 정답률 33% · 푼 사람 3,548명 (2026-09-30 기준)1

문제

중복 없는 단어 N개를 학습한 자동완성이 있다. 어떤 단어를 찾으려면, 친 글자로 시작하는 학습 단어가 그 단어 하나만 남을 때까지 쳐야 한다. 다른 단어의 앞부분이 곧 그 단어라면 끝까지 쳐야 한다. 모든 단어를 하나씩 찾을 때 쳐야 하는 글자 수의 합을 돌려준다.

  • 2 ≤ N ≤ 100,000, 단어 길이 합 2 ~ 1,000,000, 소문자만

풀이

막히면 한 단계씩 펼친다.

필요한 개념

트라이: 칸마다 “이 앞부분으로 시작하는 단어 수”를 적어 두면, 단어를 한 글자씩 따라가다 그 수가 1이 되는 순간이 멈출 곳이다.

1단계 · 작은 예로 손으로 풀기

단어 go, gone, guild

  • go: g로 시작하는 단어 3개, go로 시작하는 단어 2개(go, gone). 2글자를 다 쳤다. go는 gone의 앞부분이라 더 줄일 수 없다. → 2
  • gone: g(3), go(2), gon(1)! 여기서 하나만 남는다. → 3
  • guild: g(3), gu(1)! → 2

합은 7이다. “몇 글자째에 그 앞부분을 가진 단어가 나 하나뿐이 되나”를 세면 된다.

2단계 · 가장 단순한 방법과 그 속도

단어마다 모든 다른 단어와 공통 앞부분 길이를 재면 N² = 100억 쌍이다. 어림없다. 정렬하면 공통 앞부분이 가장 긴 단어는 바로 앞뒤 단어라 \(O(\text{글자 수} \times \log N)\)으로 줄일 수도 있지만, 트라이가 더 곧바르다.

3단계 · 핵심 아이디어
  • 트라이에 수 적기: 단어를 넣으며 지나는 칸마다 수를 1씩 늘린다. 칸의 수 = 그 앞부분으로 시작하는 단어 수다.
  • 단어마다 따라가기: 단어를 한 글자씩 내려가다 칸의 수가 1이면 거기까지 친 글자 수가 답이다. 끝까지 1이 안 되면(다른 단어의 앞부분이면) 단어 길이만큼 친다.
  • 칸의 수가 1이면 “이 앞부분을 가진 단어는 나뿐”이라는 뜻이라, 자동완성이 바로 나를 추천한다.
4단계 · 코드 흐름
  1. 빈 트라이를 만들고, 단어마다 글자를 따라 내려가며 칸의 수를 1씩 늘린다.
  2. 단어마다 다시 내려가며, 수가 1인 칸을 처음 만나면 그 위치 + 1을 더한다. 끝까지 못 만나면 단어 길이를 더한다.
5단계 · 파이썬 코드 
def solution(words):
    root = {}
    for w in words:
        node = root
        for ch in w:
            if ch not in node:
                node[ch] = [0, {}]           # [지나는 단어 수, 자식들]
            node[ch][0] += 1
            node = node[ch][1]
    total = 0
    for w in words:
        node = root
        typed = len(w)                       # 끝까지 쳐야 하는 경우가 기본
        for i, ch in enumerate(w):
            cnt, kids = node[ch]
            if cnt == 1:                     # 이 앞부분을 가진 단어가 나뿐
                typed = i + 1
                break
            node = kids
        total += typed
    return total
  • 칸을 [수, 자식 딕셔너리] 리스트로 두었다. 개념 문서처럼 딕셔너리 칸을 써도 된다.
  • cnt, kids = node[ch]: 리스트의 두 값을 한 번에 꺼낸다.
6단계 · 실행 추적

words = [word, war, warrior, world]. 트라이의 칸별 수는 w 4, wo 2, wor 2, word 1, worl 1, wa 2, war 2, warr 1이다.

단어 따라간 칸의 수 친 글자 수
word w 4, o 2, r 2, d 1 4
war w 4, a 2, r 2(끝) 3
warrior w 4, a 2, r 2, r 1 4
world w 4, o 2, r 2, l 1 4

합은 15다.

7단계 · 복잡도와 흔한 실수

넣기와 따라가기 모두 글자 수 합 L에 비례해 \(O(L)\)이다. 단어 약 10만 개(길이 합 약 100만)로 재 보니 0.3초 안팎이었다.

  • 다른 단어의 앞부분인 단어(go, war)를 끝까지 쳐야 한다는 것을 빼먹어 0이나 틀린 값을 더한다.
  • 수를 단어 끝 칸에만 적어, 중간 칸에서 “몇 개가 지나가나”를 알 수 없다.
  • 단어마다 다른 모든 단어와 비교해 시간 초과가 난다.
검증: 문제의 예시 3개를 통과했고, 6단계의 단어별 친 글자 수를 코드로 확인했다. 무작위 단어 묶음 2,000개(글자 a·b, 길이 6 이하)에서 “단어마다 다른 단어와의 가장 긴 공통 앞부분 + 1(단어 길이 이하)”로 센 값과 같았다 — 14_pg17685_p1.py

  1. 프로그래머스 스쿨, “[3차] 자동완성” (https://school.programmers.co.kr/learn/courses/30/lessons/17685), 2026-09-30 조회. ↩