[Programmers] 크레인 인형뽑기 게임 문제

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

문제를 처음 봤을 때 2차원 배열에 익숙하지 않아서 어떻게 인형을 뽑아야하나 생각하느라 오래걸렸다.

 

📖문제 설명

크레인을 작동하면 해당 라인의 가장 상위에 있는 인형이 무조건 뽑히고,(만약 해당 라인에 인형이 하나도 없으면 아무것도 뽑지 않는다.)

인형은 바구니에 담기고 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라진다.

터트려져 사라진 인형의 개수를 구해야한다.

 

입출력 예시

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

 

뽑기 board는 가로로 위에서 아래로 내려옵니다.

moves의 순서대로 크레인을 내려서 인형을 뽑으면 바구니에 이런식으로 쌓이게 됩니다.

moves 1,5,3,5,1,2,1,4

바구니 4,3,1,1,3,2,0,4

 

이 때 바구니의 3번째와 4번째 인형(1)이 같기때문에 인형이 터져서 사라지게 됩니다.

그 다음으로 2번째와 3번째의 인형(3)이 같아지기때문에 인형이 터져서 사라지게 됩니다.

즉, 총 터져서 사라진 인형의 개수는 4개이다.

 

🧑‍💻코드구현 순서

1. 바구니의 역할을 stack으로 해보았습니다.

• stack을 선언한 후 stack에 0을 넣어줍니다. 0을 넣어준 이유는 stack의 맨 위 값과 비교를 해야하는데 값이 null이면 오류가 나기 때문에 넣어줍니다.

 

2. moves의 길이만큼 for문을 돌린다.

• board의 길이만큼 for문을 돌린다.
  • board[j][move-1]이 0이면 인형 없음
  • 0이 아니면 stack의 가장 위 요소와 board[j][move-1]가 같은지 비교
  • 같으면 인형이 터져서 사라지므로 바구니(stack)에서 인형을 하나없애고(pop) answer에 더하기 2
  • 인형이 같지않다면 바구니(stack)에 board[j][move-1] 인형을 넣어준다.(push)

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        
        for(int move : moves) {
            for (int j = 0; j < board.length; j++) {
                if (board[j][move - 1] != 0) {
                    if (stack.peek() == board[j][move - 1]) {
                        stack.pop();
                        answer += 2;
                    } else {
                        stack.push(board[j][move - 1]);
                    }
                    board[j][move - 1] = 0;
                    break;
                }
            }
        }
        return answer;
    }
}