프로그래머스 크레인 인형뽑기 게임 자바

문제

풀이

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        List<Stack<Integer>> arr = new ArrayList<>();
        Stack<Integer> tmp = null;
        for(int i = 0; i < board[0].length; i++){
            arr.add(new Stack<>());
        }
        for(int i = board.length-1; i >=0 ; i--){
            for(int y = 0; y < board[i].length; y++){
                tmp = arr.get(y);
                if(board[i][y] == 0){
                    continue;
                }
                tmp.push(board[i][y]);    
            }
            
        }
        Stack<Integer> result = new Stack<>();
        for(int i = 0; i < moves.length; i++){
            tmp = arr.get(moves[i]-1);
            if(tmp.isEmpty()){
                continue;
            }
            Integer now = tmp.pop();
            
            if(result.isEmpty()){
                result.push(now);
                continue;
            }
            Integer top = result.peek();
            
            if(now == top){
                answer += 2;
                result.pop();
                continue;
            }
            
            result.push(now);
        }
        return answer;
    }
}

리뷰

인형은 맨 위에서부터만 뽑을 수 있고, 옮겨 담는 바구니는 가장 아래칸부터 순서대로 쌓인다는 글을 통해 스택을 사용하는 문제라는 것을 알 수 있다.

1. 리스트를 선언해 각 인덱스에 스택을 초기화 한다.

2. board에 들어있는 인형을 스택에 담아준다.

   • 이때 0은 비어있는 칸이므로 저장하지 않는다.

3. 인형을 옮겨 담을 바구니(스택)을 추가로 선언한다.

4. moves 배열을 탐색하며 각 바구니의 인형을 하나씩 옮겨담는다.

   • 만약 현재 탐색중인 바구니가 비어있다면 다음 반복문으로 넘어간다.
   • 비어있지 않다면 가장 맨 위의 인형을 뽑는다.
   • 만약 옮겨담는 바구니가 비어있다면 인형을 담고 다음 반복문으로 넘어간다.
   • 그렇지 않다면 옮겨담는 바구니의 맨 위 인형을 확인한다.
   • 만약 현재 뽑은 인형과 옮겨담는 바구니의 맨 위 인형이 같다면
     answer에 2를 더하고, 옮겨담는 바구니의 맨 위에 있는 인형을 제거한다.
   • 위의 모든 요건을 충족하지 않을 경우(현재 뽑은 인형과 옮겨담는 바구니의 맨 위 인형이 다를 경우)
     현재 인형을 옮겨담는 바구니에 담아준다.

헷갈렸던 부분

1. 행과 열의 순서
   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]] 이런 값이 들어왔을 때,
   [0,0,0,0,0]에서 요소는 각자 다른 바구니에 담겨져 있는 상태이다.
   
   위의 그림처럼 빨간 원이 배열에서 하나의 행인데,
   처음했던 풀이에서는 스택에 열을 기준으로 인형을 담는게 아니라 위의 그림에서처럼 행을 기준으로 인형을 담아 제시하는 순서와 바뀐 상태로 각 바구니에 인형이 담겼던 것이다.
   그래서 행을 기준으로 리스트에서 스택을 가져오는 것이 아니라 열을 기준으로 리스트에서 각 스택을 가져와야 기존에 제시한 순서대로 인형을 담을 수 있게 된다.

2. 인형을 담는 순서
   board라는 배열을 0번째 인덱스부터 탐색을 하며 스택에 담게되면 아래와 같이 스택에 쌓이게 된다.
   
   따라서 배열을 탐색할 때는 board.length -1부터 0까지 거꾸로 탐색을 해야 기존에 제시했던 순서대로 각 바구니에 인형이 쌓이게 된다.