Level1_크레인 인형뽑기 게임 (JAVA)

코딩테스트 연습 - 크레인 인형뽑기 게임

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int[] doll = new int[board[0].length];

        for(int i=0; i<board[0].length; i++){ //열
            int j=-1; //행
            while(true){
                ++j;
                if(j<board.length && board[j][i]!=0){
                    doll[i] = j;
                    break;
                }
                if(j==board.length && board[j][i]==0){
                    doll[i] = board.length+1; //비어있음
                    break;
                }
            }
        }

        Stack<Integer> stack = new Stack<>();
        int answer = 0;

        for(int i=0; i<moves.length; i++){
            int n = moves[i]-1;

            if(doll[n]<board.length){
                if(!stack.isEmpty()){
                    int temp = board[doll[n]][n];
                    int top = stack.peek();

                    if(temp == top){
                        answer += 2;
                        stack.pop();
                    }
                    else
                        stack.push(temp);
                }
                else
                    stack.push(board[doll[n]][n]);

                board[doll[n]][n] = 0;
                doll[n] += 1;
            }
        }
        return answer;
    }
}

 

문제 내 그림으로 힌트를 줬다. 스택을 쓰라는 힌트!!

 

 

내가 푼 방식을 간단하게 요약하면,

- 인형이 위치한 곳을 배열로 저장하고, 크레인 위치에 따라 인형이 위치한 곳으로 바로 이동한다.

- 인형을 뽑아 스택에 푸쉬/팝하며 터트릴 수 있는 인형의 개수를 센다.

 

 

 

조금더 자세히 설명하자면 다음과 같다.

 

1. 인형이 들어있는 자리를 매번 찾아야하는 과정을 없애기 위해 - doll[] 배열에 인형이 위치한 곳을 저장한다.

 

   예를 들면,

   3행 0열에 들어있는 인형을 doll[열]=행 으로, doll[0]=3 과같은 형태로 저장한다.

   만약 해당 열에 인형이 들어있지 않다면 - board.length+1==행 크기+1 로 저장한다.

 

 

2. moves[]배열을 하나씩 읽어가며, 인형뽑기를 진행한다.

 

   1) moves[]의 값은 '열+1'의 값이고, 그러므로 doll[열] 값을 확인한다.

      예를 들면,

      moves값 = 1 일 때 : doll[0]=3 이므로, 3행의 인형을 뽑는 것이다.

      만약 doll[n]=5라면, 5=board.length+1이므로 인형이 존재하지 않는다.

 

   2) 해당 doll[열] 값과 스택의 top과 비교해서, push여부를 결정한다.

       doll[열] == stack.peek() 이라면, 인형이 터트려지기 때문에, push하지 않고, pop + answer+2를 해준다.

       같지 않다면, push