크레인 인형뽑기 게임

문제

 

결과

 

풀이

import java.util.*;
 
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int j=0; j<moves.length; j++) {
            int doll = 0;
            
            for(int k=0; k<board.length; k++) {
                if(board[k][moves[j]-1] != 0) {
                    doll = board[k][moves[j]-1]; 
                    board[k][moves[j]-1] = 0; //뽑았으니 0으로
                    
                    break;
                }
            }
            
            //중복 검사 -> 연속해서 같은 숫자일 때만!! 사라짐
            if(stack.size() != 0 && doll != 0) {
 
                if(stack.peek() == doll) { //이미 뽑힌 인형중에 있는지 검사
                    stack.pop();
                    answer++;
                } else {
                    stack.push(doll); //없다면 moves의 그 값을 add
                }
            
            }else if(stack.size() == 0){
                stack.push(doll);
            }    
        }
        return answer*2;
    }
}

 

문제 설명이 불친절해서 인형이 어떤 형태로 들어있는지 이해가 안 갔는데 

이차원배열이 인덱스가 낮은 순에서 높은 순으로 쌓여있는 상태이다.

 

[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] 순서대로 뽑을 것이다.

 

뽑은 것은 바구니에 모아두는데

바구니를 무엇으로 둘 것인가?

 

처음에는 같은 인형이 뽑히면 터지는 줄 알고 ArrayList를 이용했는데

"연속"한 경우에만 터지는 거였다.

 

그래서 바구니를 Stack으로 설정했다.

 

1. moves의 순서대로 인형을 뽑는다.

2. 뽑은 자리는 이제 인형이 없으니까 0으로 바꾸어준다.

3. 바구니에 인형이 담길 때 가장 위에 있는 인형이 같은 인형인지 스택을 검사한다.

3-1. 같은 인형이라면 스택에서 해당 인형을 꺼내고 answer를 1 추가한다.

3-2. 같은 인형이 아니라면 스택에 담아준다.

4. 마지막 결과낼 때 answer를 두 배처리한다. → 인형이 터질 때 2개씩 터지기 때문이다.