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

나의 풀이

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        ArrayList<Integer> basket = new ArrayList<>();
        for(int i =0; i<moves.length; i++){
            for(int j =0; j<board[0].length; j++){
                if(!(board[j][moves[i]-1]==0)){
                    basket.add(board[j][moves[i]-1]);
                    board[j][moves[i]-1]=0;
                    break;
                }    
            }
        }
           for(int k=0;k<basket.size();k++){
            if(k!=(basket.size()-1)){
                if(basket.get(k)==basket.get(k+1)){
                    basket.remove(k);
                    basket.remove(k);
                    answer+=2;
                    k=-1;
                }

            }
        }
        return answer;
    }
}

접근 방식

• int[] moves 크기만큼 반복하여 int[][]board를 조회합니다.

  • moves는 1부터 시작하는 칸의 위치를 의미합니다.
  • board의 index는 0부터 시작하므로 moves[]-1로 조회합니다.

• moves의 요소로 board를 조회할 때 인형의 유무는 0으로 구분합니다.

  한 열을 반복해서 조회하여 인형을 뽑은 경우와 인형이 없는 열을 구분하기 위함입니다.

  • 3열이 두번 조회되면 첫번째 조회에 인형이 뽑힌 위치는 0으로 전환합니다.
  • 그래야 3열의 두 번째 조회에서 다른 인형을 뽑을 수 있습니다.

• 뽑힌 인형은 list basket에 넣습니다. 연속으로 뽑힌 인형은 터트려져 사라집니다.

  • 중복된 요소를 add하기 쉽고 쌓인 순서대로 인덱스를 통해 비교하고 연속된 인형을 동시에 제거하기 위해 list를 사용하였습니다.
  • list.get을 통해 k번째와 k+1번째를 비교합니다.
  • 같으면 두 인형을 삭제해야하므로 list.remove(k)를 두 번 진행합니다. (k번째가 삭제되면 k+1번째는 k번째가 되므로)
  • answer은 사라진 인형의 갯수를 의미하므로 answer+=2
  • k를 -1로 초기화하여 basket의 크기보다 작을 때까지 다시 반복을 진행합니다.

다른 사람의 풀이

import java.util.Stack;

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

다른 사람의 접근 방식

• boards의 moves[]-1번째 열을 비교하면서 동시에 stack에 뽑은 인형을 넣는 방식
• stack에 먼저 넣지 않고 peek()으로 stack의 상위 요소와 board의 요소를 비교하여 같으면 pop()하여 연속된 인형을 제거한다.
• board 요소는 stack에 넣지 않았기 때문에 한번의 제거로 연속된 인형을 제거하는 셈.
• board의 요소를 비교하여 같지 않으면 push()하여 인형을 stack에 추가하는 방식을 반복한다.

📝 후기

• 2차원 배열 요소의 비교와 뽑은 인형의 처리 방식(list or stack)
• 인형을 쌓아서 제거하기 때문에 stack이 먼저 떠올랐으나 stack에서는 인덱스의 접근이 어렵기 때문에 먼저 인형을 저장하고 제거하는데 어려움이 있었다.
• 나중에 다른 사람의 풀이를 통해 요소 비교와 제거, 추가를 동시에 진행하는 방법을 통해 기존 해결방안의 어려움을 해결할 수 있었다.
• 그래도 나름 list로 문제를 해결하여서 다행이었다!