[2019 카카오 개발자 겨울 인턴십/Java] 크레인 인형뽑기 게임

# 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

 

목차

• 카카오 문제 해설
• 내 문제풀이(LinkedList)
• 프로그래머스 다른사람 풀이 참고(Stack)

 

카카오 문제 해설    2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설 링크

문제에 주어진 대로 구현하면 되는 문제입니다. 격자 칸에서 가장 위에 있는 인형을 찾기 위해 다음과 같은 방법을 사용할 수 있습니다.

• 인형을 집어 올릴 위치에서 0이 아닌 숫자가 나올 때까지 아래 방향으로 탐색합니다. 바닥에 도착하기 전에 인형을 발견하면 해당 위치를 0으로 만들고 바구니에 담습니다.

이때, 스택 또는 큐 등의 자료구조를 이용해서 가장 위에 있는 인형을 찾을 수도 있습니다. 예를 들어 5 x 5 크기 게임 화면의 경우 각 위치에 해당하는 스택 5개를 만들고, 가장 밑에 있는 인형부터 순서대로 넣어둡니다. 이제 가장 위에 있는 인형은 각 스택의 Top에 해당하며, 인형을 집어 올릴 때는 각 위치에 해당되는 스택에서 Pop 하면 됩니다.

집어 올린 인형을 바구니에 쌓을 때도 스택을 이용하면 됩니다. Top에 위치한 인형과 비교해서 서로 다른 인형이면 스택에 Push 하고, 같은 인형이라면 스택에서 Pop 하면서 터트려 사라지는 개수를 증가시킵니다.

 

내 문제풀이 (LinkedList)

import java.util.LinkedList;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        int N = board[0].length;
        LinkedList<Integer> basket = new LinkedList<>();

        for (int move : moves) {
            move--; // move를 1 감소시켜서 인덱스화
            for(int i=0; i<N; i++) {
                if (board[i][move] != 0) {
                    int doll = board[i][move];
                    board[i][move] = 0;
                    
                    if (basket.size() > 0 && basket.getLast() == doll) {
                        basket.removeLast();
                        answer += 2;
                    } else {
                        basket.add(doll);
                    }
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

 

프로그래머스 다른사람 풀이 참고 (Stack) (홍희표 , - , - , - 외 13 명 / 링크)

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;
    }
}