크레인 인형뽑기 게임

👀 예제로 문제 파악하기

입력 : 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]

뽑기판은 가로로 위부터 아래로 내려온다.

뽑기판을 그림으로 표현하면 위와 같이 된다.

moves 순서대로 크레인을 내려가서 뽑으면 3번째와 4번째가 1로 똑같기 때문에 사라진다.

그 후에 마지막에 있는 3과 5째로 내려오는3과 똑같기 때문에 사라진다.

총 사라지는 인형 수는 4개이다.

 

😮 알고리즘 풀이 순서

1. 바구니 역할을 해줄 stack을 준비하고, 0을 넣는다.
   • 0을 넣는 이유는 stack의 맨 위 값과 비교해야하는데 아무것도 없으면 오류가 나기 때문이다.
2. moves의 길이만큼 for문을 돌린다.
   • board의 길이만큼 for문을 돌린다. (해당 라인에서 인형을 뽑기 위해)
     • 만약 board[j][move - 1]이 0이라면 인형이 없는 것이기 때문에 넘어간다.
     • 0이 아니라면
       • Stack(바구니)의 가장 윗 요소와 board[j][move - 1]가 같은지 비교한다.
         • 같다면 인형이 터지는 것이기 때문에 Stack에 pop을 하고 answer에 2를 더한다.
         • 다르다면 Stack에 board[j][move - 1]를 push한다.
3. answer를 리턴한다.

 

👨‍💻 코드

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

    Stack<Integer> stack = new Stack<>();
    stack.push(0);

    for (int move : moves) {
      for (int j = 0; j < board.length; j++) {
        if (board[j][move - 1] != 0) {
          if (stack.peek() == board[j][move - 1]) {
            stack.pop();
            answer += 2;
          } else {
           stack.push(board[j][move - 1]);
          }
          board[j][move - 1] = 0;
          break;
        }
      }
    }
    return answer;
  }

  @Test
  public void 정답(){
    Assert.assertEquals(4, solution(new int[][]{{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}}, new int[]{1,5,3,5,1,2,1,4}));
    Assert.assertEquals(8, solution(new int[][]{{3,3,3,3,3},{3,3,3,3,3},{3,3,3,3,3},{3,3,3,3,3},{3,3,3,3,3}}, new int[]{1,5,3,5,1,2,1,4}));
    Assert.assertEquals(0, solution(new int[][]{{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}, new int[]{1,5,3,5,1,2,1,4}));

  }
}

 

 

 

풀이2

- 첫 풀이 및 정답풀이

  문제 내용이 좀 길긴 한데 천천히 읽어보면 별 문제 없다. 요점은 2차원 배열에는 1~100까지의 정수가 주어지는데, 이 정수는 서로 다른 인형들을 의미하는 것이며, 1차원 배열에는 2차원 배열의 몇 번째 열에서 인형을 뽑는지 주어진다. 여기서 뽑은 인형은 LIFO 구조의 바구니에 집어넣으며, 동일한 인형이 연속해서 집어넣어질 경우 두 개의 인형이 사라진다. 결국 사라진 인형의 개수를 반환하면 된다.

 

  이 문제를 처음 풀 때는 인형을 담는 바구니를 ArrayList를 통해 인형을 모두 담아 연속하는 인형을 인덱스로 참조해 제거하는 방식을 사용하고자 했는데, 잘 생각해보니 인형이 1,2,2,1과 같은 순으로 들어갔다면 2번 인형들이 지워지고 그 자리에 1번이 내려와 또 다시 1번 인형들이 지워져야 하는 점을 만족시킬 수 없었다. 

 

  결국 바구니를 모두 채운 뒤 인형을 제거하는 것이 아니라, 채우면서 제거해야 위와 같은 상황이 발생하지 않는다는 것을 알 수 있었다. LIFO 자료구조인 Stack의 peek()메소드를 적절히 이용하면 가능할 것 같았다.

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        // 1. 연속된 인형들이 제거된 횟수.
        int answer = 0;
        // 2. 인형을 담을 stack 바구니.
        Stack<Integer> stack = new Stack<>();       
        
        // 3. moves의 크기는 크레인의 총 이동횟수.
        for(int i =0;i<moves.length;i++){
            // 3-1. j 인덱스를 이용해 보드의 행을 탐색. 열은 moves의 원소를 이용해 탐색.
            for(int j=0;j<board.length;j++){
                // 3-2. j행의 moves의 크레인위치 열에 해당하는 값에 인형이 존재한다면.
                if(board[j][moves[i]-1] != 0 ) {                   
                    // 3-3. stack이 비어있지 않고, 현재 스택의 최상단에 있는 인형과 크레인으로 뽑은 인형이 같다면
                    if(!stack.empty() && stack.peek() == board[j][moves[i]-1]){
                        // 인형들을 제거하는 횟수 증가.
                        answer++;
                        // 바구니에 있는 인형을 제거.
                        stack.pop();
                        // 크레인으로 뽑은 인형을 0으로 만들어 없애준다.
                        board[j][moves[i]-1] = 0;
                        break;
                    // 3-4. 그 외의 경우는 인형을 바구니에 담은 후 0으로 없애준다.    
                    }else{
                        stack.push(board[j][moves[i]-1]);                      
                        board[j][moves[i]-1] = 0;
                        break;
                    }
                }                        
            }
        }
        
       
        // 4. 없앤 인형의 수 = 인형을 없앤 수 * 2.
        return answer*2;
    }
}