크레인 인형뽑기 게임

---

문제 분석

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

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;
    }
}