[프로그래머스,Java] Level1:크레인 인형뽑기

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

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

문제가 너무길다.. 이번문제는 링크로 띄우겠다.

 

문제분석:

 

인형이 담겨진 board와 크레인 이동 move가 입력으로 주어졋다.

 

크레인이 이동에따라서 인형이담긴 board를 위에서부터 뽑아서 바구니에다 넣을때,

 

바구니에 들어있는 인형이 2개가 겹치면 사라지게된다.

 

이 사라진 인형갯수를 세주는문제다.

 

문제풀이:

 

문제 그림을보면, 담아두는 바구니가 마치 스택의 자료구조와 흡사하다.

 

그래서 바구니로쓸 스택을 정의한다.

 

첫번째 순회는 이동을담당하는 moves 

 

  두번째 순회는 board의 길이만큼 순회한다. 

  이 과정이 필요한이유는, 크레인이 위에서부터 내려오는데, 비어있으면( 0이면) 내려오고,

  비어있지않으면 (0이아니면) 뽑아야하기때문이다.

 

인형이 있으면(0이아니면) 바구니에 들어있는 인형이 동일한지를 비교하고, 틀리면 넣고,

맞으면 삭제한뒤, 사라진갯수를 +2 해준다.

 

그리고 인형을뽑앗으면, 뽑은자리를 0으로한다(비어있음).

 

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
       Stack<Integer> s = new Stack<Integer>();
        for(int i=0; i<moves.length; i++) {
            for(int j=0; j<board.length; j++) {
                
                if(board[j][moves[i]-1] != 0) {
                    
                    // 스택이 비어있는경우 -> 해당 인형 넣기
                    if(s.isEmpty())
                        s.push(board[j][moves[i]-1]);
                    
                    // 스택이 비어있지 않는경우 -> 인형이 동일한지 아닌지 비교
                    else {
                        // 인형이 동일하면 제거 후 사라진 인형개수 +2
                        if(s.peek() == board[j][moves[i]-1]) {
                            s.pop();
                            answer += 2;
                        }
                        // 인형이 동일하지 않으면 스택에 인형 넣기
                        else {
                            s.push(board[j][moves[i]-1]);
                        }
                    }
                    // 해당 작업 끝난 후에는 인형을 빼냈으므로 0으로 만든다.(인형이 없다는 표시)
                    board[j][moves[i]-1] = 0;
                    break;
                }
            }
        }
        
        return answer;
    }
}