2. 프로그래머스 - 크레인 인형뽑기 게임 (스택)

문제 설명

게임 개발자 죠르디는 실제 인형뽑기 기계를 모바일 게임으로 구현하고자 합니다.
게임은 다음과 같은 규칙을 따릅니다:

게임 규칙

• 게임 화면은 N x N 크기의 정사각형 격자로 구성되어 있고, 각 칸은 1 x 1 크기입니다.
• 각 칸에는 인형이 하나씩 쌓여 있으며, 0은 빈 칸을 의미합니다.
• 플레이어는 크레인을 좌우로 조작하여 특정 열에 도달한 후, 해당 열에서 가장 위에 있는 인형을 집습니다.
• 인형을 집은 후에는 오른쪽 바구니에 순서대로 넣습니다.
• 바구니에는 인형이 아래에서부터 쌓이며, 같은 모양의 인형이 연속 2개 이상 쌓이면 즉시 터지며 제거됩니다.
• 인형이 없는 열을 선택하면 아무 일도 일어나지 않습니다.
• 바구니의 크기는 무한하다고 가정합니다.

---

입력 설명

• board : N x N 크기의 2차원 배열 (각 칸에는 0 또는 1~100 사이의 숫자가 들어 있음)
  • 0 : 빈 칸
  • 1~100 : 인형의 종류
• moves : 인형을 집을 열의 순서가 담긴 배열 (1-based index)

---

출력 설명

• 크레인을 모두 작동시킨 후, 바구니에서 터져서 사라진 인형의 총 개수를 반환합니다.

---

제약 사항

• board 크기: 5 이상 30 이하
• board[i][j]: 0 이상 100 이하
• moves 길이: 1 이상 1,000 이하
• moves[i]: 1 이상 board 가로 길이 이하

---

입출력 예시

java

복사편집

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] ]; moves = [1, 5, 3, 5, 1, 2, 1, 4]; result = 4

설명

• 크레인을 작동시켜 집은 인형 순서: [4, 3, 1, 1, 3, 2, 4]
• 바구니에 인형이 순서대로 쌓이다가, 같은 모양의 인형 2개가 연속되면 제거됨
• 총 2쌍(4개)이 터짐 → 결과: 4

---

목표

board와 moves가 주어졌을 때, 바구니에서 사라진 인형의 총 개수를 반환하는 solution 함수를 구현하세요.

 

---

크레인이 좌우로 이동하기 때문에 moves배열에 있는 위치를 move변수에 저장한다.

그 다음 해당 열에서 위쪽부터(0번째 행)부터 인형을 찾아주면 된다.

만일, 인형이 있는 경우 인형의 위치를 저장하고, 뽑은 인형의 위치를 0으로 만들어주면 된다.

 

만약 바구니가 비어있지 않고, 바구니 맨 위에 저장되어 있는 인형의 모양과 같은 경우 인형들을 터뜨린 후 터뜨린 개수만큼

answer 변수에 더해주면 된다.

그렇지 않은 경우 인형의 모양을 바구니에 담아주면 된다. 

 

알고리즘 코드

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> basket = new Stack<>();
        int answer = 0; // 터뜨려진 인형 개수
        
        for(int move : moves) {
            int col = move - 1; // 배열은 0부터
            
            // 해당 열에서 위쪽부터 인형 찾기
            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;  // 터뜨려진 인형 2개 카운트
                    }else {
                        basket.push(doll);
                    }
                    
                    break;
                }
                
            }
            
        }
        
        return answer;
    }
}

 

 

스택을 이용해 푸는 문제 중에 비교적 간단한 문제이다.