[64061] 크레인 인형뽑기 게임

✔ 크레인 인형뽑기 게임

[프로그래머스 64061]

문제 분석하기

배열과 스택을 이용해서 배열에 있는 인형을 가져와서 스택에 바로 앞에 존재할 경우 터뜨리면서 인형의 개수를 증가시키도록 함

손으로 풀어보기

1. 배열에서 인형을 뺄 경우 0으로 변경시킴
   • 그 줄이 모두 0이어서 인형이 없을 경우 아무런 일이 일어나지 않고 그대로 통과 
2. 배열에서 빼낸 인형을 바구니인 스택에 넣음
   • 배열에서 빼낸 인형과 스택의 맨 위에 있는 인형이 같을 경우 둘을 함께 스택에서 제거하면서 인형의 개수를 2개 증가시킴
3. 터트러져 사라진 인형의 개수를 반환

슈도코드 작성하기

board(게임 화면의 격차의 상태가 담긴 2차원 배열)
moves(인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열)
answer(크레인을 모두 작동시킨 후 터트러져 사라진 인형의 개수)
stack(집어 올린 인형을 담을 바구니)
for(i -> moves만큼) {
    for(j -> board의 크기만큼) {
        if(board[j][i - 1]가 0이 아니라면) {
            if(stack이 비어있지 않으면서 stack의 맨 위에 있는 인형이 현재 꺼낸 인형과 같다면) {
                stack.pop
                answer 2 증가
            }
            else {
                stack에 board[j][i - 1] 넣기
            }
            board[j][i - 1]를 0으로 변경
            break;
        }
    }
}
answer 반환

코드 구현하기

/**
 * 64061) 크레인_인형뽑기_게임
 */
public class L041_64061 {
    // board(게임 화면의 격차의 상태가 담긴 2차원 배열)
    // moves(인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열)
    public int solution(int[][] board, int[] moves) {
        // answer(크레인을 모두 작동시킨 후 터트러져 사라진 인형의 개수)
        int answer = 0;
        // stack(집어 올린 인형을 담을 바구니)
        Stack<Integer> stack = new Stack<>();
        for (int i : moves) {
            for (int j = 0; j < board.length; j++) {
                // board[j][i - 1]가 0이 아니라면 (인형이 존재한다면)
                if (board[j][i - 1] != 0) {
                    // stack이 비어있지 않으면서 stack의 맨 위에 있는 인형이 현재 꺼낸 인형과 같다면
                    if (!stack.isEmpty() && stack.peek() == board[j][i - 1]) {
                        // 스택에서 인형 제거
                        stack.pop();
                        // 인형 개수 2 증가
                        answer += 2;
                    }
                    // 스택이 비어있거나, stack의 맨 위에 있는 인형이 현재 꺼낸 인형과 다르다면
                    else {
                        // stack에 현재 인형 넣기
                        stack.push(board[j][i - 1]);
                    }
                    // 인형을 뽑았으므로 0으로 변경
                    board[j][i - 1] = 0;
                    break;
                }
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L041_64061 solution = new L041_64061();

        int[][] 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 } };
        int[] moves = { 1, 5, 3, 5, 1, 2, 1, 4 };

        int result = solution.solution(board, moves);

        System.out.println(result);
    }
}