[Java][프로그래머스] 크레인 인형뽑기 - 스택

크레인 인형뽑기

문제 보기

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        
        // n-1,0 계열부터 넣고, n-2,0 계열부터 다음에 넣기 
        // 그러면 n-1,0 n-2, 1 이렇게 순서대로 넣기
        int n = board[0].length;
        Stack<Integer> picked = new Stack<>();
        
        // 초기화 
        List<Stack<Integer>> stacks = new ArrayList<>();
        for(int i = 0; i < n;i++){
            Stack<Integer> stack = new Stack<>();
            for(int j = n-1; j >= 0; j--){
                int current = board[j][i];
                if(current == 0){
                    continue;
                }
                stack.push(current);
            }
            stacks.add(stack);
        }
        
        // 움직일 때마다 stack에 넣기
        for(int m : moves){
             // 가장 위에있는거랑 지금 넣을거랑 같으면 둘다 삭제
            if(!picked.isEmpty() && !stacks.get(m-1).isEmpty()){
                if(stacks.get(m-1).peek() == picked.peek()){
                    answer+=2;
                    stacks.get(m-1).pop();
                    picked.pop();
                } else{
                    // 같지 않으면 picked에 넣기 
                    picked.push(stacks.get(m-1).pop());
                }
            } else if (!stacks.get(m-1).isEmpty()){
                picked.push(stacks.get(m-1).pop());
            } else if (stacks.get(m-1).isEmpty()){
                continue;
            }
        }
        
        return answer;
    }
}

푼 방법

• 초기화: 세로 라인별로 stack을 만들어서 리스트에 저장한다.
• 스택에 먼저 넣기: [n-1][0]이 제일 끝부분에 들어가야 하므로 n-1,n-2 이렇게 해서 해당 라인 stack에 저장한다.
• 크레인을 돌아다니면서 뽑기: 뽑은 것을 picked stack에 넣는다.

이건 세 가지 경우가 있는데
1. picked의 peek(제일 위에 있는 것)이 현재 위에 있는거랑 다르면 라인이랑 뽑힌 것에서 삭제
2. 같지 않으면 picked에 넣기
3. 라인 자체가 안비어있으면 picked에 넣고 라인에서 삭제

개선할 점

stack에 넣기 전에 그냥 검사해서 하는 방법도 괜찮을 것 같은데 코드가 너무 길어진 것 같다.. 그래도 숫자 범위 자체가 그렇게 크지는 않아서 별 차이가 없을 것 같다.