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

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

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

문제 설명

이 문제는 간단한 인형뽑기 게임이다. 크레인으로 인형을 하나씩 뽑고 그 인형을 바구니에 담아놓는다. 그러다 맨 위에 있는 인형과 새로 들어온 인형이 같으면 두 인형은 사라지고 포인트가 2점 쌓인다는 심플한 게임이다.

해결 과정

먼저 바구니부터 생각해보자. 뽑아온 인형이 하나씩 쌓인다... 뭔가 떠오르는 자료구조가 있지 않은가? 바로 스택이다. 스택은 LIFO 구조로 되어있는 자료구조이기 때문에 바구니 역할과 알맞다.

그리고 board로 들어오는 배열은 2차원 배열이고 뽑는 칸을 정하는 1차원 배열 moves를 받는다. 비어있는 칸은 0이므로 단순하게 이중 for 문을 돌면서 moves에 해당하는 칸을 한 줄 씩 읽어들이면서 0이 아닌 숫자가 있으면 스택에 넣고 그 칸을 비워주면 된다. 그러다 스택의 맨 위 숫자와 새로 뽑은 숫자가 같으면 스택에서 pop한 후 answer += 2 해주면 된다.

코드

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) {
            int column = move - 1;
            
            for (int row = 0; row < board.length; row++) {
                int doll = board[row][column];
                
                if (doll == 0) continue;
                else {
                    if (!stack.isEmpty() && stack.peek() == doll) {
                        stack.pop();
                        answer += 2;
                    } else {
                        stack.push(doll);
                    }
                    board[row][column] = 0;
                    break;
                }
            }
        }
        
        return answer;
    }
}

리팩토링

다른 사람들의 답안을 보다가 필자와 같이 스택을 사용한 사람을 보았는데 댓글 중 isEmpty()로 체크하는 대신 0을 시작부터 추가하는 게 더 좋을 것 같다는 의견이 있었다. 필자도 이에 수긍이 갔고 리팩토링을 수행하였다.

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        /**
         * 스택이 비었을 때 peek() 수행 시 발생하는 예외를 막기 위해
         * isEmpty()를 수행했지만 그냥 0을 하나 넣어둠으로써 불필요한 체크를 제거
         */
        stack.push(0);
        
        for (int move: moves) {
            int column = move - 1;
            
            for (int row = 0; row < board.length; row++) {
                int doll = board[row][column];
                
                if (doll == 0) continue;
                else {
                    // !isEmpty() 제거
                    if (stack.peek() == doll) {
                        stack.pop();
                        answer += 2;
                    } else {
                        stack.push(doll);
                    }
                    board[row][column] = 0;
                    break;
                }
            }
        }
        
        return answer;
    }
}