프로그래머스[Java] - 크레인 인형뽑기 게임(Stack, 2019 카카오 개발자 겨울 인턴십)

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

프로그래머스

 

 

동적으로 사라지는게 신기해서 가져와봄 ㅎㅎ

코드

import java.util.Stack;

class Solution {
	public static 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++) {
				/* 
				 * 해당 칸에 인형이 존재하는경우
				 * ↓ 아래로 내려가므로 행의 값이 계속 바껴야함 (0,0), (1,0), (2,0) ...
				 * moves배열에 있는 요소를 board[][] 배열의 '열' 값에 넣어서 비교
				 * 배열의 인덱스는 0부터 시작하므로 -1
				 */ 
				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;
	}
}

풀이

음 문제에서부터 한개씩 제거되고, 벽이 막혀있어서 Stack을 활용하라고 하는 것 같아서 스택을 사용했다.

문제에 맞게 그대로 구현하고, 설명은 주석으로 다 달았다.

간략히 설명 & 풀이를 하면 다음과 같다.

board[][] 2차원 배열에 인형의 종류가 숫자로 주어진다. 0 ~ 100

moves[] 1차원 배열에는 몇번째 행의 인형을 빼올건지 나타낸다.

 

1) moves[] 배열에 있는 요소중 board[][]의 가장 위에 있는 인형을 제거한다.

(board[][] 배열의 행을 기준으로 판단을 해야하기 때문에 moves[]배열의 값을 기준으로 ↓ 아래로 비교하며 탐색해야한다. 값이 0일경우 인형이 없는거로 판단. 주석 참고)

 

2) 스택이 비어있으면 스택에 쌓고, 

 

3) 스택이 비어있지 않으면 스택에 쌓을지 스택에서 제거할지만 판단해주면 된다.

   - 현재 스택에 쌓인 인형과 동일한 인형일 경우 -> 스택에서 제거 후 제거한 인형 갯수 +2

   - 현재 스택에 쌓인 인형과 다른 인형일 경우 -> 스택에 그대로 쌓으면 된다.