[프로그래머스] 크레인 인형뽑기 게임

코드 힌트

1. stack을 사용하기:
   • 이유: Stack은 후입선출(LIFO, Last-In-First-Out) 구조를 가지며, 바구니의 맨 위에 있는 인형과 새로 뽑은 인형을 쉽게 비교할 수 있습니다. 인형을 뽑고 바구니에 넣거나, 바구니 맨 위의 인형을 제거하는 등의 작업을 효율적으로 수행할 수 있습니다.
2. stack이 비어있을 때와 stack의 제일 위 요소가 동일할 때:
   • stack이 비어있을 때:
     • 바구니가 비어있는 경우, 현재 뽑은 인형을 바로 바구니에 추가합니다.
   • stack의 제일 위 요소와 현재 뽑은 인형이 동일할 때:
     • 바구니의 맨 위에 있는 인형과 새로 뽑은 인형이 동일하면, 두 인형이 터져서 사라지므로 바구니 맨 위의 인형을 제거하고, 사라진 인형의 수를 증가시킵니다.
3. result에는 stack.pop()을 했을 때 2개 추가하기:
   • 이유: stack에서 pop()을 할 때, 바구니에서 두 개의 인형이 사라지기 때문입니다. 인형이 터질 때 항상 두 개씩 사라지므로 result에 2를 더해줍니다.
4. 2중 for문을 사용할 때 배열에 접근하는 방법:
   • 첫 번째 for문: moves 배열을 순회하며, 각 요소는 크레인이 작동할 열(column)을 나타냅니다.
   • 두 번째 for문: 선택된 열의 맨 위에서부터 아래로 순회하여 인형을 찾습니다. board[i][line-1]을 통해 해당 열에서 인형을 탐색합니다. line-1을 사용하는 이유는 moves 배열의 값이 1부터 시작하기 때문에, 이를 0부터 시작하는 배열 인덱스로 맞춰주기 위해서입니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        // 정사각형 보드의 크기
        int n = board.length;
        
        // 터트려져 사라진 인형의 수를 저장할 변수
        int result = 0;
        
        // 인형을 담을 바구니 (Stack 자료구조 사용)
        Stack<Integer> stack = new Stack<>();
        
        // 크레인의 움직임을 나타내는 moves 배열을 순회
        for (int line : moves) {
            // 각 열(column)의 맨 위부터 인형을 찾기 위해 순회
            for (int i = 0; i < n; i++) {
                // 보드의 해당 위치가 비어있으면 (0이면) 다음 위치로 이동
                if (board[i][line - 1] == 0) continue;
                
                // 보드의 해당 위치가 비어있지 않으면 (인형이 있으면)
                // 스택이 비어있을 때: 인형을 바구니에 추가
                if (stack.isEmpty()) {
                    stack.push(board[i][line - 1]);
                } 
                // 스택이 비어있지 않을 때: 바구니 맨 위의 인형과 현재 인형 비교
                else if (stack.peek() == board[i][line - 1]) {
                    // 동일한 인형이면 바구니에서 제거하고 사라진 인형 수를 증가
                    stack.pop();
                    result += 2; // 인형 두 개가 사라지므로 +2
                } 
                // 바구니 맨 위의 인형과 현재 인형이 다르면 바구니에 추가
                else {
                    stack.push(board[i][line - 1]);
                }
                
                // 인형을 뽑았으므로 해당 위치를 0으로 변경
                board[i][line - 1] = 0;
                break; // 다음 moves 실행
            }
        }
        
        // 최종적으로 사라진 인형의 수 반환
        return result;
    }
}