가사 검색

문제 보기 · Level 4 · 2020 KAKAO BLIND RECRUITMENT · 정답률 28% · 푼 사람 5,162명 (2026-09-30 기준)¹

문제

가사 단어 목록 words와 검색 키워드 목록 queries가 주어진다. 키워드의 ?는 아무 글자 하나와 맞는다. ?는 키워드의 앞쪽이나 뒤쪽 한쪽에만 몰려 있다(예: fro??, ??odo, ?????). 키워드마다 들어맞는 단어 수를 배열로 돌려준다.

단어 2 ~ 100,000개(중복 없음), 길이 합 ≤ 1,000,000, 소문자만
키워드 2 ~ 100,000개(중복 가능), 길이 합 ≤ 1,000,000

풀이

막히면 한 단계씩 펼친다.

필요한 개념

정렬과 정렬 기준: 같은 길이의 단어를 사전순으로 정렬하면, 앞부분이 같은 단어들이 한데 모인다.
이분 탐색: 그 덩어리의 시작과 끝을 bisect로 찾아 개수를 뺄셈으로 구한다.

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

길이 5인 단어를 정렬하면 [frame, frodo, front, frost, kakao]다. fro??에 맞는 단어는 “fro로 시작하는 5글자”다.

사전순에서 “fro로 시작하는 5글자”는 froaa 이상 frozz 이하에 모두 들어 있고, 그 사이의 단어는 모두 fro로 시작한다. 정렬된 목록에서 이 범위는 frodo, front, frost 세 개다.

????o처럼 ?가 앞에 있으면 단어와 키워드를 모두 뒤집는다. o????가 되어 “o로 시작하는 5글자”를 뒤집은 단어 목록에서 찾으면 된다.

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

키워드마다 모든 단어와 한 글자씩 비교하면 키워드 10만 개 × 단어 10만 개로 100억 번이 넘는다. 정확성은 통과해도 효율성은 못 넘는다.

3단계 · 핵심 아이디어

길이별로 나누기: 키워드와 길이가 같은 단어만 맞을 수 있다. 단어를 길이별로 모아 정렬한다.
뒤쪽 ?: ?를 a로 바꾼 문자열이 범위의 시작, z로 바꾼 문자열이 범위의 끝이다. bisect_right(끝) − bisect_left(시작)이 개수다. a ~ z를 숫자 0 ~ 25로 보면 길이가 같은 단어는 자릿수가 같은 26진수다. 그래서 사전순이 곧 수의 크기 순이고, 앞자리가 정해진 단어들은 한 구간에 모인다(진법과 자릿수).
앞쪽 ?: 단어를 뒤집은 목록도 길이별로 따로 정렬해 둔다. 키워드를 뒤집으면 뒤쪽 ?가 되니 같은 방법을 쓴다.
모두 ?: 앞쪽 ?로 처리하면 범위가 aaa…~zzz…라 그 길이의 단어가 모두 세어진다.

4단계 · 코드 흐름

길이별 딕셔너리 두 개(원래 단어, 뒤집은 단어)에 단어를 넣고 각각 정렬한다.
키워드마다: 첫 글자가 ?면 뒤집은 목록과 뒤집은 키워드를, 아니면 원래 목록과 키워드를 쓴다.
?를 a로, z로 바꾼 두 문자열로 bisect해 개수를 구한다.

5단계 · 파이썬 코드

from bisect import bisect_left, bisect_right
from collections import defaultdict

def solution(words, queries):
    fwd, rev = defaultdict(list), defaultdict(list)       # 길이별로 모은다
    for w in words:
        fwd[len(w)].append(w)
        rev[len(w)].append(w[::-1])
    for L in fwd:
        fwd[L].sort()
        rev[L].sort()
    answer = []
    for q in queries:
        if q[0] == "?":                                   # 앞이 ?면 뒤집는다
            arr, q = rev[len(q)], q[::-1]
        else:
            arr = fwd[len(q)]
        lo = q.replace("?", "a")
        hi = q.replace("?", "z")
        answer.append(bisect_right(arr, hi) - bisect_left(arr, lo))
    return answer

defaultdict(list): 없는 길이를 처음 쓰면 빈 리스트를 만들어 준다. 없는 길이의 키워드는 빈 리스트에서 찾아 0이 된다.
w[::-1]: 문자열을 뒤집는다.
bisect_right(arr, hi): hi 이하인 단어 수, bisect_left(arr, lo): lo보다 작은 단어 수다. 둘의 차가 [lo, hi] 안의 단어 수다.

6단계 · 실행 추적

words = [frodo, front, frost, frozen, frame, kakao]

키워드	쓰는 목록	범위	bisect 결과	개수
fro??	길이 5: [frame, frodo, front, frost, kakao]	froaa ~ frozz	1, 4	3
????o	길이 5 뒤집음: [emarf, oakak, odorf, tnorf, tsorf]	oaaaa ~ ozzzz	1, 3	2
fr???	길이 5	fraaa ~ frzzz	0, 4	4
fro???	길이 6: [frozen]	froaaa ~ frozzz	0, 1	1
pro?	길이 4: 없음			0

답은 [3, 2, 4, 1, 0]이다.

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

정렬 \(O(W \log W)\)(W는 단어 수, 비교마다 글자 수만큼), 키워드마다 \(O(L \log W)\)다. 단어·키워드 10만 개씩으로 재 보니 0.1초가 안 걸렸다.

길이를 나누지 않고 한 목록에서 찾아, froaa ~ frozz 사이에 있는 길이가 다른 단어(예: froz)까지 센다.
?를 z 대신 {(z 다음 글자)로 바꾸고 bisect_left를 써도 되지만, 경계를 섞어 쓰면 한 칸씩 어긋난다.
앞쪽 ? 키워드를 원래 목록에서 찾으려다 범위를 만들 수 없어 막힌다. 뒤집는 것이 열쇠다.
트라이로도 풀 수 있다. 길이별·방향별 트라이의 노드마다 “아래 단어 수”를 적어 두는 방식이다.

검증: 문제의 예시를 통과했고, 6단계의 정렬 목록과 bisect 값을 코드로 확인했다. 무작위 입력 1,500개(글자 a·b·c, 길이 4 이하)에서 “키워드마다 모든 단어와 한 글자씩 비교하는” 풀이와 결과가 같았다. 단어·키워드 10만 개의 시간도 쟀다 — 20_pg60060_p1.py

프로그래머스 스쿨, “가사 검색” (https://school.programmers.co.kr/learn/courses/30/lessons/60060), 2026-09-30 조회. ↩