문제 보기 · Level 2 · 2018 KAKAO BLIND RECRUITMENT (3차) · 정답률 62% · 푼 사람 16,634명 (2026-09-30 기준)1
문제
LZW 압축을 구현한다. 사전은 A~Z(색인 1~26)로 시작한다. 입력 앞부분에서 사전에 있는 가장 긴 문자열 w를 찾아 그 색인을 출력하고 w를 떼어 낸다. w 다음 글자 c가 남아 있으면 w+c를 새 색인으로 사전에 넣는다. 입력이 빌 때까지 되풀이해 출력한 색인 배열을 돌려준다.
- msg는 대문자만, 길이 1~1,000
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
딕셔너리와 집합: 사전은 문자열 → 색인 딕셔너리다. “이 문자열이 사전에 있나”를 바로 확인한다.
1단계 · 작은 예로 손으로 풀기
"ABAB" (사전: A = 1, B = 2, …, Z = 26)
| 남은 입력 | 사전에 있는 가장 긴 w | 출력 | 새로 넣는 것 |
|---|---|---|---|
| ABAB | A (AB는 없음) | 1 | AB = 27 |
| BAB | B (BA는 없음) | 2 | BA = 28 |
| AB | AB (방금 넣었다) | 27 | 없음 (다음 글자가 없다) |
답은 [1, 2, 27]이다. 앞에서 넣은 AB를 뒤에서 바로 써먹는 것이 압축이 되는 원리다.
2단계 · 가장 단순한 방법과 그 속도
지금 위치에서 한 글자씩 늘려 가며 사전에 있는지 확인한다. 한 번 늘릴 때 문자열을 잘라 사전에서 찾으니, 최악이어도 길이 1,000에서 수십만 번이다. 넉넉하다.
3단계 · 핵심 아이디어
문제의 과정이 곧 코드다. 핵심은 “사전에 있는 가장 긴 w”를 찾는 방법이다.
- 지금 위치 i에서 끝 j를 i + 1로 두고(한 글자는 늘 사전에 있다),
msg[i:j+1]이 사전에 있는 동안 j를 늘린다. - 멈췄을 때
msg[i:j]가 w다. j가 끝이 아니면msg[i:j+1](= w + 다음 글자)은 사전에 없으니 새로 넣는다. - 새 색인은 “지금 사전 크기 + 1”이다.
4단계 · 코드 흐름
- A~Z를 1~26으로 넣은 딕셔너리를 만든다.
- i = 0부터 끝까지:
- j를 늘려 가장 긴 w =
msg[i:j]를 찾는다. - w의 색인을 답에 넣는다.
- 남은 글자가 있으면 w + 다음 글자를 새 색인으로 넣는다.
- i를 j로 옮긴다.
- j를 늘려 가장 긴 w =
- 답을 돌려준다.
5단계 · 파이썬 코드
def solution(msg):
dic = {chr(ord("A") + i): i + 1 for i in range(26)} # A=1 … Z=26
answer = []
i = 0
while i < len(msg):
j = i + 1
while j < len(msg) and msg[i:j + 1] in dic: # 한 글자 더 늘려도 사전에 있으면
j += 1
w = msg[i:j] # 사전에 있는 가장 긴 문자열
answer.append(dic[w])
if j < len(msg):
dic[msg[i:j + 1]] = len(dic) + 1 # w + 다음 글자
i = j
return answer
ord("A")는 글자 A의 번호(65),chr(65 + i)는 i번째 대문자다.{… for i in range(26)}: 딕셔너리 컴프리헨션으로 A~Z를 한 번에 넣는다.len(dic) + 1: 지금 사전에 26개가 있으면 27이 새 색인이다.
6단계 · 실행 추적
"KAKAO"
| i | w | 출력 | 새로 넣는 것 |
|---|---|---|---|
| 0 | K | 11 | KA = 27 |
| 1 | A | 1 | AK = 28 |
| 2 | KA | 27 | KAO = 29 |
| 4 | O | 15 | 없음 |
답은 [11, 1, 27, 15]다.
7단계 · 복잡도와 흔한 실수
위치마다 w를 늘리며 문자열을 잘라 찾으니 최악 \(O(L^2)\) 정도다(L ≤ 1,000).
- 마지막 w 뒤에 글자가 없는데도 사전에 넣으려다 범위를 넘는다.
- 색인을 0부터 시작한다. 문제는 A = 1이다.
- 가장 긴 w가 아니라 처음 찾은 한 글자만 쓴다.
검증: 문제의 예시 3개를 통과했고, 무작위 대문자 문자열 3,000개를 압축한 뒤 LZW 풀기(복원) 코드로 되돌리면 원래 문자열이 나오는 것을 확인했다 — 04_pg17684_p1.py