[코딩테스트 연습] 크레인 인형뽑기 게임

크레인 인형뽑기 게임 - 2019 카카오 개발자 겨울 인턴십

출처 - 프로그래머스(Programmers)

 

내용이 길어서 필요한 부분만 적었습니다.

문제 원본은 '프로그래머스' 에서 보시면 될 것 같습니다.

 

(제 풀이는 맨 마지막에 있습니다.)

 

문제 : 게임 화면은 1 X 1 크기의 칸들로 이루어진 N X N 크기의 정사각 격자이며,

위쪽의 크레인으로 인형을 집어 뽑은 인형은 우측 바구니에 담기게 됩니다.

 

 

위 사진과 같은 형태이며, 각 격자 칸에는 다양한 인형이 있고, 인형이 없는 칸은 빈칸 입니다.

게임 사용자는 크레인을 좌우로 움직여 멈춘 위치의 가장 위에 있는 인형부터 뽑을 수 있습니다.

 

집어 올린 인형은 우측 바구니에 쌓이게 되는데, 이때 바구니의 가장 아래 칸 부터 인형이 쌓이게 됩니다.

 

다음은 1번, 5번, 3번 위치의 인형을 순서대로 뽑은 모습입니다.

여기서 조건이 있습니다.

 

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 바구니에서 사라지게 됩니다.

위 그림의 상태에서 5번 위치의 인형을 뽑을 경우, 바구니에 "네오"가 연속으로 쌓이면서 터지게 되는 거죠.

 

바구니의 크기는 인형을 모두 담을 수 있을 만큼 충분히 크다는 가정 입니다.

 

게임 화면의 격자의 상태가 담긴 2차원 배열 board

인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves 가 매개변수로 주어질 때,

크레인을 모두 작동 시켰을 때, 바구니에서 사라진 인형의 개수를 return 하도록 완성해주세요.

 

제한 사항

- board 배열은 2차원 배열 크기로 5X5 이상 30X30 이하

- board 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.

  0은 빈칸, 1 ~ 100의 숫자는 각각의 인형

- moves 배열의 크기는 1이상 1000이하

- moves 배열 각 원소들의 값은 1 이상이며, board 배열의 가로 크기 이하인 자연수

 

입출력 예시

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]

]

 

moves

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

 

result = 4

 

다음 Solution.java 를 완성시키면 됩니다.

 

class Solution {

   public int solution(int[][] board, int[] moves) {

      int answer = 0;

 

      return answer;

   }

}

 

저는 아래와 같이 ArrayList를 사용해서 풀었습니다.

 

import java.util.ArrayList;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;

        //해당 ArrayList 는 바구니 라고 생각하시면 됩니다.         
        ArrayList result = new ArrayList<>();

 

        //일단 크레인을 작동시킨 수 만큼 반복문을 돌립니다.
        for (int i = 0; i < moves.length; i++) {

 

            //빈칸이 아닌 인형이 있는 곳을 찾을 때 까지 반복문을 돌립니다.
            for (int j = 0; j < board[0].length; j++) {

 

                //위에서 부터 차례로 검사하여 0이 아니라면 인형을 찾은 것으로 간주합니다.
                if (board[j][moves[i] - 1] != 0) {
                    if (result.size() > 0) {

                        //바구니(result)에 인형이 먼저 담겨있었다면, 마지막에 담긴 인형과 현재 뽑은 인형을 비교.
                        if (result.get(result.size() - 1) == board[j][moves[i] - 1]) {

                            //인형이 같을 경우 사라지게 되니, 뽑은 인형은 담지 않고 마지막에 담겨 있던 인형을 제거.
                            result.remove(result.size() - 1);

                            //또한, 두 인형이 사라지는 것이니 answer에 2를 더하여 줍니다.
                            answer += 2;
                        } else {

                            //마지막 담긴 인형과 뽑은 인형이 다르다면 뽑은 인형을 그대로 바구니(result)에 담습니다.
                            result.add(board[j][moves[i] - 1]);
                        }
                    } else {

                       //바구니(result)의 크기가 0 이라는 것은 첫번째 인형이므로 비교하지 않고 담아 줍니다.
                        result.add(board[j][moves[i] - 1]);
                    }

 

                    //마지막으로 해당 위치의 인형을 뽑았으니, board에서 해당 위치를 빈칸(0) 으로 만들어 줍니다.
                    board[j][moves[i] - 1] = 0;
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

단순하게 포문 두개를 사용해서 풀었습니다.

아직 코딩 테스트 공부를 시작한지 얼마 안되어서 단순하게라도 결과를 내는데에 의미를 두고 있습니다.