[프로그래머스 64061번] 크레인 인형뽑기 게임 (JAVA)

Programmers - [64061] 크레인 인형뽑기 게임

---

🖍 크레인을 작동시킨 후 터트려져 사라진 인형의 개수를 출력하는 문제
(link) 64061 (2019 카카오 개발자 겨울 인턴십) 크레인 인형뽑기 게임 (Lv.1)

 

---

[풀이 과정]

'맨 위의 인형을 뽑고, 차례대로 넣고, 터트린다.' 라는 사실을 통해 어떤 자료구조를 사용해야 할 지 감을 잡을 수 있다.

스택을 사용하면 간단하게 풀 수 있는 문제. 스택은 대표적인 후입선출(LIFO) 자료구조이다.

 

인형들이 담긴 격자 정보가 들어있는 2차원 배열 변수 board[][] 가 있고, 크레인의 위치가 저장된 배열 moves[] 가 있다.

우리는 moves에 저장된 숫자를 열 번호로 지정하여 크레인을 가로로 움직이고, 격자에 든 인형을 보기 위해 board의 세로 길이(=열 길이) 만큼 탐색을 할 것이다.

따라서 첫 번째 반복문에서 moves의 길이 만큼 반복하고, 두 번째 반복문에서 board의 열 길이 만큼 반복한다. 이때, 두번째 반복문에서 열 인덱스는 고정하고 행 인덱스만 유동 변수로 지정하여, 지정된 열 한 줄을 탐색하게 할 것임.

말이 조금 어려운데 결국 moves에 저장된 숫자로 열 인덱스를 정하고, 열 길이 만큼 반복을 하는 것은 위 그림의 노란색 한 줄을 탐색한다는 것과 같다.

 

 

그 다음,

스택으로 만들어야 하는 것은 바구니이다. 크레인이 인형을 뽑았을 경우 바구니에 인형을 넣게 되는데, 이 때 바구니의 최상단에 위치하는 것과 같은 숫자이면 바구니에서 그 두 인형을 터트리기 때문에 스택의 pop 연산이 필요하다.

<참고, 스택의 메소드>

push(data) -> data를 스택에 쌓음

peek() -> 스택 최상단의 data를 반환

pop() -> 스택 최상단의 data를 지움

------

 

그리고 조건문을 나눠주면 된다.

 

(1) 0을 만났을 경우

0의 경우 빈칸이므로, 건너뛰고 다음 탐색을 진행한다. (continue)

 

(2) 크레인이 만난 숫자와 바구니 최상단의 숫자가 같은 경우

크레인이 만난 숫자가 스택에 들어가게 되면 같은 숫자가 닿으므로 터지는 상황이다. 이럴 때는 뽑은 숫자를 굳이 스택에 push 연산할 필요 없이 스택에서 한 번 pop해주면 된다. 크레인이 인형을 뽑았으므로 해당 자리는 0으로 바꿔주고 터트린 인형 개수를 세어 저장한다.

크레인이 인형을 뽑으면 해당 열은 탐색을 중지한다. (break)

 

(3) 크레인이 만난 숫자가 바구니 최상단의 숫자와 다른 경우

이 경우는 그냥 스택에 해당 숫자를 push해준다. 크레인이 인형을 뽑았으니 해당 자리를 0으로 만들어주고 탐색을 중지하는 것도 잊지 않기.

 

이 과정을 반복하여 최종 정답 개수를 구하고 반환하면 끝.

 

---

[Pseudocode]

1. 스택(=바구니) 선언
2. 스택에 초기연산을 위한 0값 넣기
3. for i : 0 ~ moves.length // 열 번호 지정
	4. for j : 0 ~ board[i].length // 행 번호 지정
    	// (1) 0이면 건너뛰기
        5. if (board[j][moves[i-1]] == 0) continue; 
        // (2) 스택과 일치하면 pop 후 0으로 교체
        6. else if (board[j][moves[i-1] == stack.peek()])
        	7. stack.pop
        	8. board[j][moves[i-1] = 0
        	9. answer += 2
        	10. break;
        // (3) 스택과 일치하지 않으면 push
        11. else
        	12. stack.push(board[j][moves[i-1]];
        	13. break;
14. answer 반환

---

[Code]

import java.util.*;

/**
 * 프로그래머스 64061번
 * 크레인 인형뽑기 게임
 * 
 */
public class Problem16 {
    public static void main(String[] args) {
        int[][] board = {{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}};
        int[] moves = {1,5,3,5,1,2,1,4};
        System.out.println(solution(board, moves));
    }

    public static int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> basket = new Stack<>(); // 바구니
        basket.push(0); // 초기 peek 연산을 위해 값 넣기

        // moves 크기 만큼 인형뽑기 시도
        for (int i=0 ; i<moves.length ; i++) {
            // 인형을 만날 때까지 board의 세로 길이 만큼 탐색
            for(int j=0 ; j<board.length ; j++) {
                // 1. 크레인이 내려오면서 0인지 확인
                if(board[j][moves[i]-1] == 0)
                    continue;

                // 2. 크레인이 만난 인형이 바구니 최상단 인형과 같을 때
                else if(board[j][moves[i]-1] == basket.peek()) { 
                    basket.pop(); // 인형을 넣지 않고 바로 stack 에서 pop
                    board[j][moves[i]-1] = 0; // 인형이 뽑힌 자리이므로 0으로 초기화
                    answer += 2; // 인형 두 개가 터짐
                    break;
                }
                
                // 3. 크레인이 다른 인형을 만났을 때
                else {
                    basket.push(board[j][moves[i]-1]); // 바구니에 추가
                    board[j][moves[i]-1] = 0; // 인형이 뽑힌 자리이므로 0으로 초기화
                    break;
                }
            }
        }
        return answer;
    }
}

 

---

[Result]

---

(2021.07.29 풀이분)

스택을 이용한 레벨1 문제이다 보니까 당시에도 어렵진 않았음.