[프로그래머스] 크레인 인형뽑기 게임 (스택 level 1)

문제

크레인을 작동하면 해당 라인의 가장 상위에 있는 인형이 무조건 뽑히고, (만약 해당 라인에 인형이 하나도 없으면 아무것도 뽑지 않는다)

인형은 바구니에 담는다. 이 때 인형이 연속으로 2개 있으면 터져서 사라진다.

뽑기판 board이 주어지고 뽑는 라인의 순서인 moves이 주어질 때,

터져서 사라진 인형의 갯수를 구해야한다.

 

 알고리즘 풀이 순서

1. 바구니 역할을 해줄 stack을 준비하고, 0을 넣는다.
   • 0을 넣는 이유는 stack의 맨 위 값과 비교해야하는데 아무것도 없으면 오류가 나기 때문이다.
2. moves의 길이만큼 for문을 돌린다.
   • board의 길이만큼 for문을 돌린다. (해당 라인에서 인형을 뽑기 위해)
     • 만약 board[j][move - 1]이 0이라면 인형이 없는 것이기 때문에 넘어간다.
     • 0이 아니라면
       • Stack(바구니)의 가장 윗 요소와 board[j][move - 1]가 같은지 비교한다.
         • 같다면 인형이 터지는 것이기 때문에 Stack에 pop을 하고 answer에 2를 더한다.
         • 다르다면 Stack에 board[j][move - 1]를 push한다.
3. answer를 리턴한다.

import java.util.*;


class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0; // 제거된 인형 갯수

        Stack<Integer> stack = new Stack<>(); //인형을 담을 바구니 
        stack.push(0); // 0을 넣는 이유는 stack의 맨 위 값과 비교해야하는데 아무것도 없으면 오류 발생 방지

        for(int move : moves){// moves = 총 이동횟수만큼 반복
            for(int i=0; i< board.length; i++){ // i 인덱스를 이용해 보드의 행 탐색, 열은 move를 이용해 탐색
                if(board[i][move-1] !=0){ //인형이 있는 경우
                if(stack.peek() == board[i][move-1]){ //최근 인형과 들어오는 인형이 같으면 없애고 2추가
                    stack.pop();
                    answer +=2;
                }else{
                    stack.push(board[i][move-1]);//같지 않으면 인형을 push
                }
                board[i][move-1]=0; //그리고 뽑은 인형은 0으로 없애줌 
                break;
            }
        }
    }
        return answer;

}
}