[알고리즘]프로그래머스 64061번 - 크레인 인형뽑기 게임

프로그래머스 64061번 - 크레인 인형뽑기 게임

프로그래머스 64061번 - https://programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스 64061번 - https://programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스 64061번 - https://programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스 64061번 - https://programmers.co.kr/learn/courses/30/lessons/64061

 

요구사항

1. 크레인을 작동시킨 후, 해당 멈춘 위치에서 가장 위에 있는 인형을 집어 바구니에 차곡차곡 쌓습니다.

2. 동일한 인형이 바구니에 연속적으로 쌓인 경우, 두 인형은 터지며, 작업이 끝날 때까지 터트려져 사라진 인형의 개수를 반환하라.

3. 격자(board)에 인형이 없을 경우 0, 있을 경우 인형의 종류를 나타내는 번호가 담겨있습니다.

 

요구사항 분석 및  풀이과정

1. 크레인을 움직인 후 크레인을 내려 인형이 있을 경우(격자에 담긴 값이 0이 아닌 경우) 격자에서 제거한 후, 바구니에 담습니다.

2-1. 바구니가 비어있을 경우 그냥 담고, 바구니가 비어있지 않을 경우 바구니의 가장 위의 인형과 담을 인형의 종류를 비교합니다.

2-2. 동일한 인형이 연속적으로 쌓일 경우, 두 인형을 터트리며 바구니에서 제거하고 터뜨린 인형의 개수를 2개 늘립니다.

2-3. 동일한 인형이 아닐 경우, 바구니에 그냥 담습니다.

3. 위의 작업을 크레인의 모든 작업에 대해서 수행합니다.

 

바구니를 밑에서 위로 차곡차곡 쌓고, 연속된 인형을 터뜨릴 경우 바구니의 가장 최근에 쌓인 인형을 제거하는 것이므로 바구니는 스택 자료구조를 사용하는 것이 합리적입니다.

 

소스코드 작성

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {

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

        for(int move : moves) {
            int col = move - 1;

            for(int row = 0; row < board[0].length; row++) {
                int doll = board[row][col];

                if (doll != 0) {
                    board[row][col] = 0;

                    if (!buffer.isEmpty() && buffer.peek() == doll) {
                        buffer.pop();
                        answer += 2;
                        break;
                    }

                    buffer.push(doll);
                    break;
                }
            }            
        }

        return answer;
    }
}

 

결과

 

소스코드 깃허브 주소

링크