프로그래머스 크레인 인형뽑기 게임 JAVA 풀이 (2019 카카오 개발자 겨울 인턴십)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

크레인을 좌우로 이동시키며 선택한 열의 가장 위에 있는 인형을 뽑아 바구니에 담습니다.

바구니에 같은 모양의 인형이 연속해서 들어오면 두 인형이 터지며 사라집니다.

 

모든 크레인 동작이 끝난 뒤 사라진 인형의 개수를 반환하는 문제입니다.

---

📌 접근 방법

이 문제는 시뮬레이션과 Stack을 함께 사용하는 대표적인 문제입니다.

1. moves를 순회하며 크레인이 이동할 열을 선택합니다.
2. 해당 열을 위에서 아래로 탐색하여 가장 먼저 발견되는 인형을 찾습니다.
3. 인형을 꺼낸 뒤 해당 위치를 0으로 변경합니다.
4. 바구니(Stack)의 가장 위 인형과 비교합니다.
   • 같으면 제거하고 answer += 2
   • 다르면 Stack에 추가합니다.
5. 인형 하나를 처리했다면 break로 다음 move를 수행합니다.

---

📌 핵심 아이디어

1. 바구니는 Stack으로 구현

바구니는 마지막에 들어간 인형과만 비교하면 되므로 Stack이 가장 적합합니다.

Stack<Integer> basket = new Stack<>();

 

---

2. 선택한 열에서 가장 위 인형 찾기

열은 고정하고 행을 위에서 아래로 탐색합니다.

for (int row = 0; row < board.length; row++) {
    if (board[row][col] != 0) {
        ...
    }
}

---

3. 인형 제거 처리

같은 인형이 연속되면 Stack에서 제거하고 개수를 증가시킵니다.

if (!basket.isEmpty() && basket.peek() == doll) {
    basket.pop();
    answer += 2;
}

---

4. 이미 뽑은 인형은 0으로 변경

같은 인형을 다시 뽑지 않도록 처리합니다.

board[row][col] = 0;

---

5. 인형 하나를 뽑으면 탐색 종료

한 번의 크레인 동작은 인형 하나만 가져갈 수 있습니다.

break;

 

---

📌 전체 코드

import java.util.Stack;

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

        for (int move : moves) {
            int col = move - 1;

            for (int row = 0; row < board.length; row++) {
                if (board[row][col] != 0) {
                    int doll = board[row][col];
                    board[row][col] = 0;

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

                    break;
                }
            }
        }

        return answer;
    }
}

 

---

📄 정리

• Stack을 사용하면 바구니의 마지막 인형을 효율적으로 관리할 수 있다.
• peek()로 같은 인형인지 확인하고 pop()으로 제거한다.
• 인형을 뽑은 위치는 0으로 변경해야 중복으로 뽑히지 않는다.
• 한 번의 크레인 동작에서는 인형 하나만 뽑으므로 break가 반드시 필요하다.
• 시뮬레이션과 Stack을 함께 연습하기 좋은 대표적인 문제이다.