섹션 5. Stack, Queue - 3. 크레인 인형뽑기(카카오)

📌 문제 설명

크레인 인형뽑기 기계를 모바일 게임으로 구현하려고 합니다.

N x N 격자에 인형들이 쌓여 있으며, 사용자 입력에 따라 크레인이 특정 열에서 인형을 집어 바구니에 넣습니다. 바구니에는 인형이 순서대로 쌓이며, 같은 모양의 인형이 연속으로 두 개 쌓이면 터지며 사라집니다.

이때 사라진 인형의 총 개수를 구하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수 N (5 ≤ N ≤ 30)
• 다음 N줄에 N x N 크기의 2차원 배열 board가 주어집니다 (0은 빈칸, 1~100은 인형)
• 다음 줄에 moves 배열의 길이 M (1 ≤ M ≤ 1000)
• 마지막 줄에 크레인의 작동 순서를 나타내는 moves 배열

출력

• 사라진 인형의 총 개수 출력

---

🔹 예제 입력 & 출력

예제 입력 1

5
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
8
1 5 3 5 1 2 1 4

 

예제 출력 1

4

---

💡 해결 방법

• 크레인을 moves 배열 순서대로 작동시킵니다.
• 각 열의 가장 위에 있는 인형을 찾아 바구니(Stack)에 넣습니다.
• Stack에 이미 같은 인형이 있는 경우 두 인형을 터뜨리고, 사라진 인형의 수를 2만큼 증가시킵니다.
• 인형이 없으면 아무 작업도 하지 않습니다.

---

💻 코드 구현 (Java)

package partStackQueue;

import java.util.Scanner;
import java.util.Stack;

public class Problem3 {
	public int solution(int n, int[][] arr, int m, int[] moves) {
		int answer = 0;
		Stack<Integer> stack = new Stack<>();
		
		for(int j : moves) {
			for(int i = 0; i < n; i++) {
				int doll = arr[i][j-1];
				if(doll != 0) {
					arr[i][j-1] = 0;
					if(!stack.isEmpty() && stack.peek() == doll) {
						stack.pop();
						answer += 2;
					} else {
						stack.push(doll);
					}
					break;
				}
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Problem3 T = new Problem3();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[][] arr = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				arr[i][j] = kb.nextInt();
			}
		}
		int m = kb.nextInt();
		int[] moves = new int[m];
		for(int i = 0; i < m; i++) {
			moves[i] = kb.nextInt();
		}
		System.out.print(T.solution(n, arr, m, moves));
		kb.close();
	}
}

---

📖 코드 설명

Stack<Integer> stack = new Stack<>();

• 바구니 역할을 하는 Stack을 생성합니다.

for(int j : moves) {
	for(int i = 0; i < n; i++) {
		int doll = arr[i][j-1];
		...
	}
}

• moves 배열에 따라 각 열을 위에서부터 탐색합니다.
• 0이 아닌 인형을 발견하면 처리하고, 더 이상 해당 열을 탐색하지 않습니다.

if(!stack.isEmpty() && stack.peek() == doll) {
	stack.pop();
	answer += 2;
} else {
	stack.push(doll);
}

• Stack의 최상단과 현재 인형이 같으면 둘 다 터뜨립니다.
• 아니면 바구니에 인형 추가

---

⏳ 시간 복잡도 분석

• moves 배열의 길이를 M, board의 크기를 N이라 할 때
• 각 move에 대해 최대 N번 탐색 → O(NM)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런