문제 보기 · Level 1 · 2019 카카오 개발자 겨울 인턴십 · 정답률 55% · 푼 사람 50,231명 (2026-09-30 기준)1
문제
N×N 격자에 인형이 아래부터 쌓여 있다. 크레인을 moves에 적힌 열 순서대로 내려 그 열의 맨 위 인형을 집어 바구니에 쌓는다. 빈 열이면 아무 일도 없다. 바구니에 같은 인형 두 개가 연달아 쌓이면 둘 다 터져 사라진다. 사라진 인형 수를 돌려준다.
- board 5×5~30×30. 0은 빈칸, 1~100은 인형 종류
- moves 길이 1~1,000
풀이
막히면 한 단계씩 펼친다2.
1단계 · 작은 예로 손으로 풀기
board는 위쪽 줄부터 적는다. 열은 1번부터 센다.
0 0 0
0 1 0
2 1 3
moves = [2, 2, 1, 3]
| 크레인 | 집은 인형 | 바구니 (오른쪽이 맨 위) | 터진 수 |
|---|---|---|---|
| 2번 열 | 1 | [1] | 0 |
| 2번 열 | 1 | 맨 위도 1 → 둘 다 터짐, [] | 2 |
| 1번 열 | 2 | [2] | 2 |
| 3번 열 | 3 | [2, 3] | 2 |
답은 2다. 한 번 터질 때 인형은 두 개 사라진다.
2단계 · 가장 단순한 방법과 그 속도
크레인을 내릴 때마다 그 열을 위에서부터 훑어 처음 나오는 인형을 찾는다. 한 번에 최대 30칸, 1,000번이면 3만 칸이다. 넉넉하다. 이 문제는 규칙을 정확히 옮기면 된다.
3단계 · 핵심 아이디어
- 바구니 = 스택. 새 인형은 바구니의 맨 위하고만 비교한다. 같으면 맨 위를 꺼내고(pop) 터진 수에 2를 더한다. 다르면 쌓는다(push).
- 열의 맨 위 인형. 위쪽 줄(0번)부터 내려가며 0이 아닌 첫 칸이 맨 위 인형이다. 집으면 그 칸을 0으로 바꾼다.
- moves는 1부터 센 열 번호라
m - 1로 바꿔 쓴다.
4단계 · 코드 흐름
- 빈 바구니 리스트와 터진 수 0을 준비한다.
- moves의 열마다 위쪽 줄부터 내려가며 0이 아닌 칸을 찾는다.
- 찾으면 그 칸을 0으로 만들고, 바구니 맨 위와 같으면 꺼내고 2를 더한다. 다르면 쌓는다. 한 개만 집으므로 찾은 즉시 멈춘다.
- 끝까지 찾지 못하면(빈 열) 아무것도 하지 않는다.
- 터진 수를 돌려준다.
5단계 · 파이썬 코드
def solution(board, moves):
basket = []
popped = 0
n = len(board)
for m in moves:
col = m - 1 # 1부터 센 열 → 0부터
for row in range(n): # 위에서 아래로
doll = board[row][col]
if doll != 0:
board[row][col] = 0 # 집어 올린다
if basket and basket[-1] == doll:
basket.pop() # 같은 인형 두 개가 터진다
popped += 2
else:
basket.append(doll)
break # 한 번에 하나만
return popped
break: 안쪽for만 멈추고, 다음 move로 넘어간다.basket and basket[-1] == doll: 바구니가 비어 있으면 뒤를 보지 않는다.- 이 코드는 입력
board를 직접 고친다. 원래 격자가 다시 필요하면 먼저 복사한다.
6단계 · 실행 추적
문제의 예시(board 5×5, moves = [1, 5, 3, 5, 1, 2, 1, 4])를 따라가면 집는 인형은 차례로 4, 3, 1, 1, 3, 2, (1번 열은 이제 빔), 4다.
| 집은 인형 | 바구니 | 터진 수 |
|---|---|---|
| 4 | [4] | 0 |
| 3 | [4, 3] | 0 |
| 1 | [4, 3, 1] | 0 |
| 1 | 맨 위 1과 같음 → [4, 3] | 2 |
| 3 | 맨 위 3과 같음 → [4] | 4 |
| 2 | [4, 2] | 4 |
| (빈 열) | [4, 2] | 4 |
| 4 | [4, 2, 4] | 4 |
답은 4다.
7단계 · 복잡도와 흔한 실수
move M개마다 열을 최대 N칸 훑으니 \(O(MN)\)이다. 열마다 인형을 스택으로 미리 만들어 두면 \(O(N^2 + M)\)으로 줄일 수 있지만, 이 제한에서는 필요 없다.
- 터질 때 1을 더한다. 인형은 두 개 사라진다.
break를 빼먹어 한 열에서 인형을 여러 개 집는다.- 집은 칸을 0으로 바꾸지 않아 같은 인형을 또 집는다.
검증: 문제의 예시를 통과했고, 무작위 격자 2,000개에서 “열마다 인형 스택을 미리 만드는” 다른 풀이와 결과가 같았다 — 10_pg64061_p1.py