[프로그래머스] 크레인 인형뽑기 게임 - JAVA

 

 

풀이

import java.util.Stack;

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

 

 

이 문제는 stack을 사용하면 쉽게 풀 수 있다.

풀면서 헷갈리게 만드는 점이 두 가지 있었는데 풀면서 문제가 참 불친절하다고 생각했다...

우선 제일 헷갈렸던 건 행렬인데 i가 행, j가 열인 줄 알고 풀었다가 대차게 틀리고 그림을 그려보고 확실하게 이해하게 됐다.

 

문제의 예시를 인형뽑기 크레인처럼 놓아본다면 아래와 같다.

 

Row 0: 0 0 0 0 0  <-- 가장 위쪽 (행 4)
Row 1: 0 0 1 0 3  <-- 행 3
Row 2: 0 2 5 0 1  <-- 행 2
Row 3: 4 2 4 4 2  <-- 행 1
Row 4: 3 5 1 3 1  <-- 가장 아래쪽 (행 0)

 

 

그래서 행/열을 바꿔 board[j][i-1]를 구해야 문제를 풀 수 있다.

board[j][i-1]이 0이 아니면 item 변수에 board[j][i-1]의 값을 넣고 해당 칸에서는 인형을 뽑았기 때문에 0을 대입한다.

stack이 비어있지 않고 stack의 마지막 값과 현재 item의 값이 동일하면 stack.pop()을 사용해 맨 위(뒤)의 값을 제거한다.

 

문제에서는 제거한 인형의 수를 계산하는 것이기 때문에 answer에는 2를 더해줘야 한다.

위의 조건에 만족하지 않으면 stack에 방금 뽑아온 인형(board[j][i-1]의 값)을 추가하면 된다.