[programmers] 크레인 인형뽑기 게임(Java)_2019 카카오 개발자 겨울 인턴십

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

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

---

# 문제 요약

크레인에 들어있는 죠르디 인형을 moves 배열에 담긴 순서대로 뽑아, 바구니에 담는다.

바구니에 담긴 죠르디 인형들은 stack 형태로 들어가며, 이웃한 같은 인형들끼리는 터트려진다.

이때, 터트려진 인형의 개수를 return하는 문제

 

# 풀이

stack 사용

시간복잡도 : O(N*N)

 

# 코드

import java.util.Stack;

class Solution {
    public static int solution(int[][] board, int[] moves) {
        Stack<Integer> baguni = new Stack<Integer>(); // 바구니
        final int N = board.length; // 크레인 크기
        int M = moves.length; // 총 바구니에 들어가는 죠르디의 개수

        for(int m: moves){
            for(int i=0; i<N; i++) {
                // 작동 위치에 해당하는 크레인 데이터를 위에서부터 확인
                if(board[i][m-1]>0){
                    baguni.push(board[i][m-1]); // 바구니에 죠르디 넣음
                    board[i][m-1]=0; // 해당 위치 크레인 비우기
                    matchBaguni(baguni); // 바구니 안에 이웃한 같은 죠르디가 있다면, 터트리기
                    break;
                }

                // 크레인의 마지막 바닥까지 탐색해도,
                // 죠르디가 없다면, 바구니에 담지 못했다는 의미이므로
                // 총 바구니에 들어갔었던(?) 죠르디의 개수를 -1 줄임
                if(i==N-1) M-=1;
            }
        }
        // 총 바구니에 들어간 죠르디의 개수 - 바구니에 남아있는 죠르디 개수 = 터트린 죠르디 개수
        return M - baguni.size();
    }

    /**
     * 죠르디 터트리기
     * - 바구니의 TOP, TOP-1에 위치한 죠르디가 같다면, 터트리기
     * @param baguni: stack.push로 들어오는 죠르디
     * */
    public static void matchBaguni(Stack<Integer> baguni){
        int prevIdx = baguni.size()-2;
        
        // 바구니에 들어있는 죠르디 개수가 1이라면, prevIdx = -1 이므로 확인할 필요없음
        if(prevIdx < 0) return;
        if(baguni.peek() == baguni.get(prevIdx)){ // TOP, TOP-1 위치에 같은 죠르디인지 확인
            // 터트리기
            baguni.pop(); // 펑!
            baguni.pop(); // 펑!
        }
    }
}