💡크레인 인형뽑기 게임

🔗 프로그래머스 - 크레인 인형뽑기 게임

---

🧠 문제파악

인형들이 쌓여 있는 2차원 배열 board가 있고,
크레인이 인형을 뽑는 순서가 들어있는 배열 moves가 주어진다

크레인이 이동할 때마다 해당 열에서 가장 위에 있는 인형을 뽑아서
바구니(stack)에 넣는데,
바구니의 마지막 인형과 같은 인형이 연속으로 쌓이면 터져서 사라져.

터진 인형 개수 × 2가 최종 점수

즉,

• 인형을 뽑는다.
• 바구니에 넣는다.
• 연속된 같은 인형이면 둘 다 사라진다.

이 과정을 반복하는 시뮬레이션 문제

---

💡 접근방법

1. 스택(Stack) 을 이용하자.

   • 인형을 하나씩 바구니에 넣되,
     이전 인형이랑 같으면 둘 다 제거.

2. moves를 하나씩 순회하면서,

   • 해당 열을 위에서부터 탐색 → 0이 아닌 값(인형)을 발견하면 뽑기.
   • 뽑은 자리는 0으로 만들기.
   • 바구니의 top과 비교해서 같으면 제거, 다르면 push.

3. 제거된 횟수를 세고, 마지막에 2를 곱해 리턴.

구분	내용
자료구조	Stack
시간복잡도	O(n²) (board 전체 탐색 가능)
공간복잡도	O(n)
포인트	단순 구현 + 스택 응용

---

🧩 문제풀이 (Java)

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> basket = new Stack<>();
        int removed = 0;

        for (int move : moves) {
            int col = move - 1; // 1-based → 0-based
            for (int row = 0; row < board.length; row++) {
                if (board[row][col] != 0) {
                    int doll = board[row][col];
                    board[row][col] = 0; // 인형 뽑았으니 0으로 초기화

                    if (!basket.isEmpty() && basket.peek() == doll) {
                        basket.pop();
                        removed += 2;
                    } else {
                        basket.push(doll);
                    }
                    break;
                }
            }
        }
        return removed;
    }
}