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

 

 

📑 1. 문제설명

---

💡 2. 풀이 과정

문제 예시처럼 5*5 격자가 있다고 가정 해 보면 격자의 가장 아래 칸부터 인형이 차곡차곡 쌓여 있고, 가장 위에 있는 인형을 집어 올릴 수 있다. 이 문제에서 "집어 올린 인형은 바구니에 쌓이는데 바구니의 가장 아래 칸부터 인형이 순서대로 쌓인다."라는 부분을 보면 스택 문제인 걸 바로 알 수 있다.

 

게임화면이나 바구니를 스택이라고 생각하면 된다. 문제는 board 배열을 스택으로 변환시키는 것이 어렵다. 만약에 값이 0이 들어오면 빈 칸이기 때문에 스택에 넣지 않는다. 그리고 크레인이 인형을 꺼내는 것은 stack.pop()으로 구현할 수 있다.

 

인형뽑기 게임 로직

 

1. 바구니가 빈 경우 -> 무조건 푸시

2. 바구니가 비지 않은 경우

  2-1. 바구니의 가장 위에 있는 인형과 지금 넣으려는 인형이 같은가?

    2-1-1. 같다 → stack.pop() 후 사라진 인형은 2개이다. 따라서 answer+=2;

    2-2-2. 다르다 → stack.push() 스택에 인형을 넣는다.

3. return answer

 

예시 배열 그림으로 보기

 

 

아직 크레인이 동작하지 않은 초기 상태는 위와 같다.

여기서 [1, 5, 3, 5, 1, 2, 1, 4] 순서로 크레인을 움직여 인형을 뽑는다.

---

1. 첫 번째 시도 (1)

 [1, 5, 3, 5, 1, 2, 1, 4] 

바구니가 비었기 때문에 크레인이 첫번째 스택에서 인형4를 집어서 바구니에 푸시한다.

---

2. 두 번째 시도 (5)

[5, 3, 5, 1, 2, 1, 4] 

5번째 스택에서 인형 3을 집어서 바구니에 푸시한다. 이 때부터는 가장 최근에 푸시한 인형과 숫자를 비교해서 같은 인형이면 둘다 제거한다. 3 != 4이므로 그대로 푸시한다.

---

3. 세 번째 시도 (3)

[3, 5, 1, 2, 1, 4] 

스택 3에서 인형1을 집어서 바구니에 넣는다. 바구니 맨 위의 인형과 값이 다르므로 그대로 둔다 (1 != 3)

---

4. 네 번째 시도 (5)

[5, 1, 2, 1, 4] 

 

스택5에서 인형을 집어 옮기며 같은 작업을 한다. 바구니 맨 위의 인형과 옮긴 인형이 1번으로 같기 때문에 바구니 안의 인형을 팝한다. 그리고 스택5에서 집은 인형도 사라지므로 2개의 인형이 사라진다. 그래서 없어진 인형을 뜻하는 변수 answer에는 2개의 카운트가 올라가게 된다.

---

5. 다섯 번째 시도 (1)

[1, 2, 1, 4] 

또 스택 1에서 인형 3을 집어서 바구니로 옮긴다. 이 때도 바구니 맨 위의 인형이 3번으로 번호가 같기 때문에 팝하고, 집은 인형도 지운다. 없어진 인형 +2를 해서 4가 된다.

---

6. 여섯 번째 시도 (2)

[2, 1, 4] 

두 번째 스택에서 인형 2를 바구니로 옮긴다.

 

---

7. 일곱 번째 시도 (1)

[1, 4] 

첫 번째 스택에는 인형이 하나도 없기 때문에 아무 동작도 일어나지 않는다.

---

8. 여덟 번째 시도 (4)

[4] 

마지막으로 4번째 스택에서 인형 4를 뽑아서 바구니에 옮긴다. 직전에 바구니에 들어온 인형과 비교했지만 인형의 숫자가 동일하지 않아서 그대로 푸시한다. (4 != 2)

 

문제에서 주어진 예시 배열대로 인형을 뽑은 후 최종 화면의 모습은 위와 같다. 

---

⭐ 3. 정답코드

public int solution(int[][] board, int[] moves) {
    int answer = 0; // 터진 인형의 총 개수 (2개씩 사라짐)
    Stack<Integer> stack = new Stack<>(); // 뽑은 인형을 저장할 스택

    // 'moves' 배열의 각 이동에 대해 반복
    for (int move : moves) {
        // 각 열을 순차적으로 확인 (board.length는 행의 개수)
        for (int j = 0; j < board.length; j++) {
            // 현재 위치에 인형이 있다면 (0이 아닌 값)
            if (board[j][move - 1] != 0) {
                int doll = board[j][move - 1]; // 해당 위치의 인형을 가져옴

                // 스택이 비어있지 않고, 스택의 맨 위 인형과 현재 인형이 같으면
                if (!stack.isEmpty() && stack.peek() == doll) { 
                    stack.pop(); // 인형을 터뜨리기 위해 스택에서 제거
                    answer += 2; // 같은 인형이 터져서 2개가 사라짐
                } else {
                    stack.push(doll); // 스택에 인형을 추가
                }

                board[j][move - 1] = 0; // 뽑은 인형은 해당 위치에서 제거 (0으로 설정)
                break; // 한 번에 하나의 인형만 뽑을 수 있으므로 반복문을 탈출
            }
        }
    }

    return answer; // 터진 인형의 총 개수 반환
}

 

 

자꾸 런타임 오류가 나서 몇 번 고쳤다. IndexOutOfBoundsException이나 NullPointerException에 주의해야 한다.

특히 board의 열 인덱스와 move 배열을 처리하는 부분에서 인덱스에 신경써야 한다.

 

⭐ board[j][move - 1] != 0에서 move - 1을 사용하는 이유

 

인덱스가 0부터 시작하기 때문이다.

 

현재 moves 배열에는 각 열에서 인형을 뽑는 순서가 들어있는데, 예를 들어, moves = [1, 5, 3, 2]라면 첫 번째, 다섯 번째, 세 번째, 두 번째 열에서 인형을 뽑겠다는 의미이다.

 

하지만 자바에서 배열 인덱스는 0부터 시작하기 때문에, move 값이 1일 때는 board 배열에서 0번째 열을 참조해야 한다. 그래서 따라서 move - 1을 사용하여 1이 들어있는 moves 배열 값을1-based 에서 0-based 인덱스로 변환해 주는 것이다.

---

⭐여기서 !stack.isEmpty()를 하는 이유

if (!stack.isEmpty() && stack.peek() == doll) { 
    stack.pop();
    answer += 2; // 같은 인형이 겹쳐서 터지면 2개가 사라짐
}

 

스택이 비어있을 때 peek()을 호출하면 EmptyStackException 예외가 발생하기 때문이다. 

이걸 방지하려면 !stack.isEmpty()를 하거나 stack.push(0);로 더미 값(0)을 추가해야 한다.처음부터 0을 넣어두면, stack.peek()를 호출할 때 항상 비교할 값이 존재한다. 

Stack<Integer> stack = new Stack<>();
System.out.println(stack.peek()); // java.util.EmptyStackException 발생!

---