[Programmers] Lv.1 | 크레인 인형뽑기 게임 풀이 | Java

스택 시뮬레이션 완전 정리

https://school.programmers.co.kr/learn/courses/30/lessons/64061

---

1. 문제 설명

대표적인 시뮬레이션 + 스택 문제

게임 규칙 자체는 단순

• 특정 열에서 가장 위 인형 선택
• 바구니에 넣기
• 같은 인형 연속 시 제거

하지만 실제 구현에서는 아래 실수가 자주 발생

• 인덱스 처리 실수
• 이미 뽑은 인형 재사용
• 스택 비교 처리 누락
• break 위치 실수

특히 중요한 부분은 board 의미 이해

• 많은 사람이 처음에 헷갈리는 부분
• board 는 단순 입력값이 아니라 현재 게임판 상태 자체를 의미
• 즉 인형을 뽑으면 반드시 board 값도 변경해야 함

---

2. 핵심 아이디어

핵심은 두 가지

• 현재 열에서 가장 위 인형 찾기
• 바구니 마지막 인형과 비교하기

바구니는 가장 마지막에 들어간 인형만 확인하면 됨

즉 LIFO 구조 필요

따라서 스택 사용이 가장 적합

 

또한 board 자체가 현재 게임 상태이므로 인형을 뽑은 뒤 반드시 0 처리 필요

그리고 인형 하나를 뽑았다면 현재 move 작업 즉시 종료 필요

이 부분에서 break 역할 중요

---

3. 풀이 방법 비교

1) List 사용

가능은 함

하지만 마지막 원소 제거 및 비교가 핵심이라

의미상 스택이 더 적절

---

2) Stack 사용

가장 직관적 방법

다만 Java Stack 클래스는 오래된 구조

내부적으로 synchronized 처리 존재

코딩테스트에서는 보통 더 가벼운 구조 사용

---

3) ArrayDeque 사용 ← 최적 선택

스택처럼 사용 가능

• push()
• pop()
• peek()

모두 O(1)

실무와 코테에서 가장 많이 사용하는 방식

---

4. 최적 풀이 선택 이유

최악의 경우 계산

• board 최대 30 x 30
• moves 최대 1000

모든 move 마다 최대 30칸 탐색

즉

1000 × 30 = 30000

연산량 매우 작음

충분히 안전

추가 자료구조도 스택 하나만 사용

메모리 부담도 거의 없음

---

5. board 구조 먼저 이해하기

문제를 이해할 때 가장 중요한 부분

많은 사람이 board 를 단순 입력 배열로 생각함

하지만 실제로는 현재 게임판 상태 자체

 

예시

[
 [0,0,0,0,0],
 [0,0,1,0,3],
 [0,2,5,0,1],
 [4,2,4,4,2],
 [3,5,1,3,1]
]

여기서 세로 방향으로 보면

1열 : 4 → 3
2열 : 2 → 2 → 5
3열 : 1 → 5 → 4 → 1

처럼 아래부터 인형이 쌓인 상태

---

예를 들어 1열에서 인형 하나를 뽑으면

원래 상태

[0]
[0]
[0]
[4]
[3]

가장 위 인형인 4 선택

그 이후에는 반드시

[0]
[0]
[0]
[0]
[3]

으로 바뀌어야 함

그래야 다음에는 3 이 뽑힘

즉 아래 코드가 반드시 필요

board[row][column] = 0;

이 부분 빠뜨리면 이미 뽑은 인형을 또 뽑는 버그 발생

실전에서 가장 흔한 실수 중 하나

---

6. break 가 왜 필요한지 이해하기

이 부분도 구현 실수 매우 많이 발생

문제 조건 다시 보면

크레인은 한 번 움직일 때
해당 열에서 가장 위 인형 딱 1개만 뽑을 수 있음

즉 move 하나당 인형 하나만 처리 가능

---

예시

[0]
[1]
[2]
[3]

현재 move 가 1열이라고 가정

반복문은 위에서 아래로 탐색

for (int row = 0; row < board.length; row++)

진행 과정

row = 0 -> 빈칸
row = 1 -> 인형 1 발견

여기서 이미 인형 하나를 뽑았음

따라서 이번 move 작업 끝

즉 아래 2, 3 까지 계속 탐색하면 안 됨

그래서 반드시 즉시 종료 필요

그 역할이 break

---

만약 break 없으면 문제 발생

1도 뽑고
2도 뽑고
3도 뽑는 버그 발생

즉 한 번 move 에서 여러 개를 뽑게 됨

실전 구현 문제에서 break 위치는 매우 중요

---

7. Java 코드

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {

    public int solution(int[][] board, int[] moves) {

        // 최종적으로 터진 인형 개수 저장
        int removedDollCount = 0;

        // 바구니 역할 수행
        // 가장 마지막 인형만 비교하면 되므로 스택 구조 사용
        // Stack 보다 ArrayDeque 가 더 빠르고 가벼움
        Deque<Integer> basket = new ArrayDeque<>();

        // 사용자가 크레인을 움직인 순서대로 진행
        for (int move : moves) {

            // 문제는 1번부터 시작
            // 배열 인덱스는 0번부터 시작
            // 따라서 -1 보정 필요
            int column = move - 1;

            // 현재 열의 가장 위 인형 찾기
            // 위에서 아래 방향으로 탐색
            for (int row = 0; row < board.length; row++) {

                // 현재 위치 값 저장
                // 0이면 빈칸
                // 1~100이면 인형 번호
                int currentDoll = board[row][column];

                // 빈칸이면 다음 칸 탐색
                if (currentDoll == 0) {
                    continue;
                }

                // 인형을 뽑았으므로 기존 위치 제거
                // 이 코드가 없으면 같은 인형을 또 뽑게 됨
                // 즉 board 는 단순 입력값이 아니라
                // 현재 게임 상태 자체라고 이해해야 함
                board[row][column] = 0;

                // 바구니 최상단 인형과 비교
                // peek() 은 제거 없이 값만 확인 가능
                if (!basket.isEmpty() && basket.peek() == currentDoll) {

                    // 같은 인형이면 제거
                    basket.pop();

                    // 인형 2개가 동시에 터짐
                    removedDollCount += 2;

                } else {

                    // 다른 인형이면 바구니에 추가
                    basket.push(currentDoll);
                }

                // 현재 move 에서는 인형 하나만 뽑을 수 있음
                // 따라서 현재 작업 즉시 종료
                // break 가 없으면 아래 인형까지 계속 뽑는 버그 발생
                break;
            }
        }

        return removedDollCount;
    }
}

 

---

8. 시간복잡도 & 공간복잡도

시간복잡도

• moves 순회 → O(M)
• 각 move 마다 최대 N 탐색

최종

O(M × N)

최대 연산

1000 × 30 = 30000

시간초과 위험 없음

---

공간복잡도

바구니 최대 크기 기준

O(N²)

최대 900개 수준

충분히 안전

---

9. 최적화 포인트

• ArrayDeque 사용으로 Stack 대비 성능 개선
• 인형 찾으면 즉시 break
• board 직접 수정으로 추가 메모리 제거
• continue 사용으로 빈칸 빠른 스킵
• 불필요한 객체 생성 없음
• 모든 연산 O(1) 수준 유지

실전 코딩테스트 기준 충분히 안정적 구조

---

10. 마무리 정리

이 문제 핵심은 세 가지

• 시뮬레이션 구현
• 스택 활용
• 상태 변화 처리

특히 중요한 부분은 아래 두 개

board[row][column] = 0;
break;

첫 번째는

이미 뽑은 인형 제거 처리

 

두 번째는

한 번 move 에서 인형 하나만 처리하기 위한 종료 처리

이 두 개 빠뜨리면 대부분 오답 발생

 

코딩테스트 구현 문제는

복잡한 알고리즘보다 상태 흐름을 정확히 구현하는 능력이 훨씬 중요함