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

1. 문제

---

프로그래머스

2. 풀이 과정

---

문제 분석

• board는 N X N의 크기이고 크레인은 1~N 사이 중 한 곳에서 인형을 뽑아 바구니에 쌓는다.

• 1 - 5 - 3 - 5 순으로 인형을 뽑는다고 한다면 다음과 같이 바구니에 들어가게 되는데 이 경우 인형1이 연속 두 번 나오므로 이 인형 두개는 동시에 사라진다.

문제 해결

• 나는 인형을 바구니에 차곡차곡 쌓고 같은 인형이 두 번 나오면 그 인형을 바구니에서 꺼낸다는 특징을 보고 스택을 떠올렸다.

1. 인형을 뽑고 바구니가 비어있거나  바구니 맨 위에 인형이 뽑은 인형과 같지 않다면 스택에 넣는다.
2. 만약 같다면 바구니 맨 위에 있는 인형을 스택에서 꺼낸다.

3. 내 코드

---

[『코딩 테스트 합격자 되기 - 자바편』 해설 코드]

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        
        Stack<Integer> basket = new Stack<>();
        int doll_cnt = 0;
        
        for(int i = 0; i < moves.length; i++) {
            for(int j = 0; j < board.length; j++) {
                if(board[j][moves[i] - 1] != 0) {
                    int doll = board[j][moves[i] - 1];
                    board[j][moves[i] - 1] = 0; // 해당 인형 뽑음 처리
                    if(!basket.isEmpty() && basket.peek() == doll) { // 바구니 맨 위의 인형이 뽑은 인형과 같으면
                        doll_cnt += 2; // 인형 터짐
                        basket.pop();
                    } else {
                        basket.push(doll); // 바구니에 인형넣기  
                    }
                    break;
                }
            }
        }
        
        return doll_cnt;
    }
}

시간복잡도

• O(N^2)

4. 다른 정답 코드와 비교

---

import java.util.Stack;

public class Solution {

    public int solution(int[][] board, int[] moves) {
        // ❶ 각 열에 대한 스택을 생성합니다.
        Stack<Integer>[] lanes = new Stack[board.length];
        for (int i = 0; i < lanes.length; i++) {
            lanes[i] = new Stack<>();
        }

        // ❷ board를 역순으로 탐색하며, 각 열의 인형을 lanes에 추가합니다.
        for (int i = board.length - 1; i >= 0; i--) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] > 0) {
                    lanes[j].push(board[i][j]);
                }
            }
        }

        // ❸ 인형을 담을 bucket을 생성합니다.
        Stack<Integer> bucket = new Stack<>();

        // ❹ 사라진 인형의 총 개수를 저장할 변수를 초기화합니다.
        int answer = 0;

        // ❺ moves를 순회하며, 각 열에서 인형을 뽑아 bucket에 추가합니다.
        for (int move : moves) {
            if (!lanes[move - 1].isEmpty()) { // 해당 열에 인형이 있는 경우
                int doll = lanes[move - 1].pop();
                // ❻ 바구니에 인형이 있고, 가장 위에 있는 인형과 같은 경우
                if (!bucket.isEmpty() && bucket.peek() == doll) {
                    bucket.pop();
                    answer += 2;
                }
                else { // ❼ 바구니에 인형이 없거나, 가장 위에 있는 인형과 다른 경우
                    bucket.push(doll);
                }
            }
        }

        return answer;
    }

}

시간복잡도

• O(N^2)

내코드와 차이점이 있다면, board 행렬의 각 열을 스택으로 변환했다는 점이다. 이렇게 하면 각 열의 인형을 뽑을 때 별도로 순회하지 않아도 된다는 장점이 있다. 따라서 인형을 뽑고 바구니에 넣는 과정이 O(N)으로 절약된다.

하지만 결국엔 스택으로 변환하는데 O(N^2)이 걸려서 최종 시간복잡도는 똑같이 O(N^2)이 나온다.

5. 피드백

---

• 차곡차곡 쌓고 위에서부터 꺼낸다는 말이 나오면 스택을 떠올리자