[프로그래머스] 크레인 인형뽑기 게임 / 2019 카카오 개발자 겨울 인턴십 - JAVA

🔗 문제 링크

[프로그래머스] 크레인 인형뽑기 게임 / 2019 카카오 개발자 겨울 인턴십

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

 

📝 풀이 과정

열마다 가장 위에 있는 인형들의 위치를 저장할 top 배열을 만들어 0이 아닌 값(인형이 존재)이 나올 때까지 내려 저장해주었다. 바구니는 위에 계속 쌓이는 형태로 Stack과 구조가 동일해 stack으로 생성해 주었다.

 

moves배열을 하나씩 탐색하며 top[move - 1]이 N과 동일하다면 빈 열이기 때문에 무시하고 넘겨주었고, 인형을 집은 경우 top배열을 하나 증가시켜주고 stack에 쌓아주었다. 만약 stack의 제일 위의 값과 동일하다면 같은 인형이므로 터지게 된다. 따라서 stack에 제일 위의 인형을 제거해주고, 답에 2를 더해주었다.

 

💻 코드

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public int solution(int[][] board, int[] moves) {
        int N = board.length;
        int[] top = new int[N];
        for (int i = 0; i < N; i++) {
            int idx = 0;
            while (idx < N && board[idx][i] == 0)
                idx++;
            top[i] = idx;
        }

        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int move : moves) {
            if (top[move - 1] >= N) continue;
            int tmp = board[top[move - 1]++][move - 1];
            if (stack.isEmpty() || stack.peek() != tmp)
                stack.push(tmp);
            else {
                stack.pop();
                ans += 2;
            }
        }

        return ans;
    }
}