문제 보기 · Level 3 · 2020 카카오 인턴십 · 정답률 53% · 푼 사람 12,926명 (2026-09-30 기준)1
문제
진열대에 보석이 한 줄로 놓여 있다. 모든 종류의 보석을 하나 이상 포함하는 가장 짧은 연속 구간을 찾아 [시작 번호, 끝 번호]로 돌려준다. 번호는 1부터 센다. 가장 짧은 구간이 여럿이면 시작 번호가 가장 작은 것을 고른다. 정확성과 효율성을 따로 채점한다.
- 보석 1~100,000개
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 투 포인터와 슬라이딩 윈도: 창의 오른쪽 끝을 늘리고, 줄일 수 있으면 왼쪽 끝을 줄인다.
- 딕셔너리와 집합: 창 안의 보석 종류별 개수.
1단계 · 작은 예로 손으로 풀기
진열대 [A, B, A, C, B] (번호 1~5), 종류는 A, B, C 세 가지
- 오른쪽 끝을 늘리다 4번(C)에서 처음으로 세 종류가 다 들어온다: 창 1~4
- 왼쪽의 A(1번)는 창 안에 A가 또 있으니 빼도 된다 → 창 2~4 [B, A, C] (길이 3)
- 2번 B는 창 안에 하나뿐이라 뺄 수 없다
- 5번(B)을 넣는다 → 이제 2번 B는 빼도 된다 → 창 3~5 [A, C, B] (길이 3)
가장 짧은 길이는 3이고, 그중 시작이 빠른 [2, 4]가 답이다.
2단계 · 가장 단순한 방법과 그 속도
모든 시작과 끝 쌍을 보면 구간이 약 50억 개(10만²/2)다. 효율성에서 떨어진다.
3단계 · 핵심 아이디어
창 밀기를 쓴다.
- 오른쪽 끝을 하나씩 늘리며 그 보석의 개수를 딕셔너리에 1 더한다.
- 창 맨 왼쪽 보석이 창 안에 2개 이상이면, 빼도 종류가 줄지 않으니 뺀다. 더 뺄 수 없을 때까지 되풀이한다.
- 창 안의 종류 수(딕셔너리 키 수)가 전체 종류 수와 같으면, 지금 창이 “이 오른쪽 끝에서 끝나는 가장 짧은 구간”이다. 지금까지의 최단보다 짧을 때만 바꾼다. 같으면 바꾸지 않으니 먼저 찾은(시작이 빠른) 구간이 남는다.
떠올리는 신호: “모든 종류를 포함하는”, “가장 짧은 연속 구간”, 그리고 10만이라는 크기.
4단계 · 코드 흐름
- 전체 종류 수 K를 센다(
len(set(gems))). - 빈 딕셔너리
count, 왼쪽 끝 left = 0, 최단 답을 무한대로 둔다. - 오른쪽 끝 right를 0부터 끝까지:
count[gems[right]] += 1count[gems[left]] > 1인 동안 왼쪽을 빼고 left += 1- 종류 수가 K이고 길이가 최단보다 짧으면 [left + 1, right + 1]로 바꾼다.
- 답을 돌려준다.
5단계 · 파이썬 코드
def solution(gems):
kinds = len(set(gems))
count = {}
left = 0
best = [1, len(gems)] # 처음엔 전체 구간
for right, g in enumerate(gems):
count[g] = count.get(g, 0) + 1
while count[gems[left]] > 1: # 왼쪽 보석이 또 있으면 빼도 된다
count[gems[left]] -= 1
left += 1
if len(count) == kinds and right - left < best[1] - best[0]:
best = [left + 1, right + 1] # 번호는 1부터
return best
- 딕셔너리에서 개수가 0이 된 키를 지우지 않아도 된다. 왼쪽을 뺄 때는 개수가 2 이상일 때만 빼서, 창 안에 있는 종류의 개수는 0이 되지 않는다.
best의 길이 비교는끝 − 시작끼리 한다. 번호를 1부터 세든 0부터 세든 차이는 같다.
6단계 · 실행 추적
[“DIA”, “RUBY”, “RUBY”, “DIA”, “DIA”, “EMERALD”, “SAPPHIRE”, “DIA”] (종류 4)
| right | 넣은 보석 | 뺀 보석 | 창 (번호) | 종류 수 | 최단 |
|---|---|---|---|---|---|
| 1~3 | DIA, RUBY, RUBY | 없음 | 1~3 | 2 | [1, 8] |
| 4 | DIA | DIA(1번), RUBY(2번) | 3~4 | 2 | [1, 8] |
| 5 | DIA | 3~5 | 2 | [1, 8] | |
| 6 | EMERALD | 3~6 | 3 | [1, 8] | |
| 7 | SAPPHIRE | 3~7 | 4 | [3, 7] | |
| 8 | DIA | 3~8 | 4 | [3, 7] (더 길다) |
답은 [3, 7]이다.
7단계 · 복잡도와 흔한 실수
두 끝이 각각 n번만 움직이니 \(O(n)\)이다.
- 같은 길이일 때 답을 바꿔 시작이 늦은 구간을 돌려준다.
- 번호를 0부터 센 채로 돌려준다.
- 종류가 하나뿐인 입력([“XYZ”, “XYZ”, “XYZ”])에서 [1, 1]이 나와야 하는데, 처음 답을 잘못 두어 틀린다.
검증: 문제의 예시 4개를 통과했고, 무작위 진열대 3,000개에서 모든 시작·끝 쌍을 보는 느린 풀이와 결과가 같았다 — 18_pg67258_p1.py