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

문제 설명

상세한 문제 설명은 프로그래머스에서 확인할 수 있습니다.

인형들이 세팅된 N x N의 2차원 배열 board에서 인형을 집어 오른쪽 바구니로 옮기는 문제입니다.

먼저 바구니로 옮겨진 인형들 위로 새로 옮긴 인형들이 쌓이는 방식인데, 같은 인형이 두 개 쌓이게 되면 해당 인형들은 사라지게 됩니다.
또한 바구니 크기는 제한이 없습니다. (최대 N * N 개의 인형이 쌓일 수도 있는 겁니다)
크레인 위치를 1~N 사이로 이동시키도록 하는 배열 moves에 따라 인형을 뽑을 때 최종적으로 사라진 인형의 개수를 구하는 문제입니다.

제한 사항

• board 배열은 2차원 배열로 크기는 5x5  이상 30x30 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예시

board	moves	result
[[0, 0, 0, 0, 0], [0, 0, 1, 0, 3], [0, 2, 5, 0, 1], [4, 2, 4, 4, 2], [3, 5, 1, 3, 1]]	[1, 5, 3, 5, 1, 2, 1, 4]	4

풀이

스택을 활용하여 풀면 간단하게 해결할 수 있는 문제입니다.
1~N 번 크레인 위치의 인형들을 세로 기준으로 나누어서 각 스택에 삽입하고 바구니 또한 스택을 활용하여 풀면 됩니다.

이때 스택의 peek(), 즉 제일 위쪽에 있는 인형이 현재 크레인에서 집어온 인형과 같다면 삭제 처리해 주면 됩니다.
삭제되는 인형의 개수는 현재 크레인에서 집어온 인형, 바구니 제일 위쪽에 있는 인형 총 2개입니다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int n = board.length;
        
		// 인형을 LIFO 순으로 뽑을 Stack List 구성
		List<Deque<Integer>> deques = new ArrayList<>();
        
		// 크레인 위치를 기준으로 각 번호에 맞는 스택에 인형을 넣어둡니다.
		for (int i = 0; i < n; i++) {
			Deque<Integer> deque = new ArrayDeque<>();
			for (int j = n - 1; j >= 0; j--) {
				if (board[j][i] != 0) {
					deque.push(board[j][i]);
				}
			}
			deques.add(deque);
		}

		// moves 배열과 규칙에 따라 계산
		int result = 0;
		Deque<Integer> stack = new ArrayDeque<>();
		for (int move : moves) {
			// 문제에서는 1번부터 시작하지만 리스트는 0번 부터 시작하기에 -1 해줍니다.
			int idx = move - 1;
            
			// idx번 위치에 더 이상 인형이 없는 경우 무시합니다.
			if (deques.get(idx).isEmpty()) {
				continue;
			}

			// idx번 위치에서 맨 위의 인형을 집습니다.
			int item = deques.get(idx).pop();
            
			// 바구니가 비어있지 않고, 바구니 맨 위 인형과 현재 집고 있는 인형이 같으면
			if (!stack.isEmpty() && stack.getFirst() == item) {
				// 삭제 처리 해줍니다.
				stack.pop();
				result += 2;
			} else {
				// 그게 아니면 바구니에 인형을 옮겨줍니다.
				stack.push(item);
			}
		}

		return result;
    }
}

N번 크레인 위치에 인형을 세팅해 줄 때 0이 등장하는 순간 해당 열의 인형 삽입을 중단할 수도 있습니다만, 1 0 2 1 3 처럼 0 이후에 인형이 담겨 있을 수도 있기 때문에 삽입 중단 로직을 작성하지 않았습니다.