[Programmers] 크레인 인형뽑기 게임

크레인 인형뽑기 게임

문제 분석

자세한 내용은 링크를 참고.

2차원 배열이 주어지고 인형들이 있다.

인형을 크레인으로 집어서 우측 바구니에 담는다.

바구니에 담을 때 같은 인형이 2개가 된다면 팡 터져서 삭제된다.

우측 바구니에 담긴 네오 인형이 2개이므로 삭제된다.

이런 규칙으로 삭제되는 인형이 몇 개인지 리턴하라.

(인형을 담은 2차원 배열, 크레인 작동 위치의 배열이 주어진다.)

풀이 과정

🎯 2차원 배열을 인형 뽑기 모양으로 보자


for (int[] line : board) {
	System.out.println(Arrays.toString(line));
}

주어진 배열을 한눈에 확인할 수 있다.

예제를 기준으로 출력을 해보면 아래와 같다.

출력 예시)


🏗️ 크레인은 여기서 집어간다. (위에서 아래로)

[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번 라인으로 크레인이 움직이면 4번 인형을 집는다.

2번 라인으로 크레인이 움직이면 2번 인형을 집는다.

3번 라인은 1번 인형

4번 라인은 4번 인형

5번 라인은 3번 인형을 집는다.

각 번호는 인형들을 뜻하고 같은 인형은 번호가 같다.

크레인은 위에서 아래로 내려오면서 인형을 집는다. (각 라인의 맨 위 인형)

라인이 비어있다면 아무 일도 일어나지 않는다.

집은 인형은 우측 바구니에 담게 된다.

🎯 우측 바구니는 스택으로 구현해보자.

스택 : 선입후출의 선형 자료 구조

기존에 있는 인형과 새로 집어온 인형이 같은지 아닌지 비교해야한다.

스택은 해당 로직을 쉽게 구현한다.


<Stack<Integer> stack = new Stack<>();
// 우측 바구니
	[  ]
	[  ]
	[  ]
	[  ]
	[  ]
	----

크레인이 집어온 인형을 스택에 추가하자.

추가할 때의 로직은 간단하다,

1. 바구니가 비어있다면 인형을 추가한다.

2. 바구니가 비어있지 않다면 맨 위 인형을 .peek() 해서 꺼내온다.

2-1. 추가할 인형과 기존의 인형이 같다면 팡 터트려준다.

2-2. 같지 않다면 인형을 스택에 .push() 해준다.

2-1. 팡 터트려줄 때 카운트를 세준다.


                if (stack.size() == 0 || stack.peek() != doll) {
                    stack.push(doll);
                    break;
                } // 1

                if (stack.peek() == doll) {
                    stack.pop();
                    answer += 2;
                    break;
                } // 2

1-1. 스택이 비어있다면 인형을 추가한다.

1-2. 스택이 비어있지않고 꺼낸 인형이 집어온 인형과 다르다면 인형을 추가한다.

2. 스택에서 꺼낸 인형과 집어온 인형이 같다면 팡 터트려주고 카운트 해준다. 이때, 터진 인형은 2개다.

나의 생각

스택의 특성을 이용하여 쉽게 풀 수 있었다.

이 문제의 핵심음 2차원 배열을 어느 방향에서 바라보느냐와

자료 구조를 이용해서 핵심 로직을 푸는 것이다.

코드


import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();

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

            for (int i = 0; i < board.length; i++) {
                if (board[i][index] == 0) continue;

                int doll = board[i][index];
                board[i][index] = 0;

                if (stack.size() == 0 || stack.peek() != doll) {
                    stack.push(doll);
                    break;
                }

                if (stack.peek() == doll) {
                    stack.pop();
                    answer += 2;
                    break;
                }

            }
        }

        return answer;
    }
}