알고리즘/문제 풀이

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

_eunji_ 2022. 2. 12. 17:14

https://programmers.co.kr/learn/courses/30/lessons/64061

 

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

[[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]] [1,5,3,5,1,2,1,4] 4

programmers.co.kr

 

문제 설명

  • 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
    "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.
  • 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다).
  • 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다.
  • 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 
  • 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.
  • 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.
  • 크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
  • 게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

  • board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
  • board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
    • 0은 빈 칸을 나타냅니다.
    • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
  • moves 배열의 크기는 1 이상 1,000 이하입니다.
  • moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

스택을 이용하여 풀 수 있는 문제이다.

스택 자료구조에 대한 간단한 메서드는 다음과 같다.

 

Stack

  • push(E item) : item을 Stack의 top에 삽입
  • pop() : top에 있는 item을 삭제하고 item을 반환
  • peek() : top에 있는 item을 삭제하지 않고 item을 반환
  • empty() : Stack이 비어있으면 true를 그렇지 않으면 false 반환
  • search(Object o) :해당 Object의 위치를 반환

 

풀이 방법

1. 바구니 역할인 stack을 선언한 뒤 0을 넣어준다 -> 처음 값과 비교할 대상이 필요하므로 0을 넣어줌

2. moves 길이와 board 길이만큼 이중 반복문을 통해  board [j][moves [i]-1]을 검사한다.

- board [j][moves [i]-1]이 0이 아닌 경우,

stack의 top 요소와 board [j][moves [i]-1] 값이 같다면 stack에서 pop을 하여 요소를 반환하고 answer값에 2를 더한다.

stack의 top 요소와 board [j][moves [i]-1] 값이 다르다면 stack에서 해당 값을 push을 한다.

또한 인형을 뽑았으므로 해당 자리의 값은 0으로 바꿔준다. ->  board[j][moves[i] - 1] = 0;

board[j][moves[i]-1]이 0인 경우, 인형이 없기 때문에 pass한다.

 

 

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        int result[]= new int[moves.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[j][moves[i]-1]!=0){
                     if (stack.peek() == board[j][moves[i] - 1]) {
                        stack.pop();
                        answer += 2;
                      }else{
                       stack.push(board[j][moves[i] - 1]);
                      }
                      board[j][moves[i] - 1] = 0;
                      break;
                }
            }
            
        }
        
        return answer;
    }
}

 

 

stack 자료구조가 생각나지 않아 arrayList로 접근했다.

 

 

풀이 방법

1. 바구니 역할인 result 리스트를 선언한다.

2. board [j][moves [i]-1]이 0이 아닐 경우 즉, 인형이 존재할 경우 result에 해당 값을 추가하고 board [j][moves [i]-1]을 0으로 수정한다.

3. 반복문을 통해 result 리스트를 검사한다.

- 인덱스 k가 리스트의 마지막 요소가 아닐 때, 해당 요소와 다음 요소의 값이 같다면 두 값을 제거하고 answer에 2를 더해준다.

- ArrayList에서 요소가 삭제되면 index가 한 칸씩 밀리기 때문에 result.remove(k); 을 두 번 반복하여 연속되는 숫자를 삭제해주고 k-1을 통해 리스트 길이도 수정한다.

 

 

다른 풀이

import java.util.ArrayList;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        ArrayList<Integer> result = new ArrayList<Integer>();

        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board.length;j++){
                if(board[j][moves[i]-1]!=0){
                    result.add(board[j][moves[i]-1]);
                    board[j][moves[i]-1]=0;
                    break;
                }
        }
        }
        
        for(int k=0;k<result.size();k++){
            if(k!=(result.size()-1)){
                if(result.get(k)==result.get(k+1)){
                    result.remove(k);
                    result.remove(k);
                    answer+=2;
                    k=-1;
                }

            }
        }

        return answer;
    }
}