[스택] 프로그래머스 크레인 인형뽑기 // 배열을 스택으로 바꿔라

https://school.programmers.co.kr/learn/courses/30/lessons/64061?language=java

프로그래머스

*풀이1

배열을 탐색하면서 0이 아닌원소를 찾고

stk에 pop하는 방식

import java.util.*;

class Solution {
    static int[][] board;
    static ArrayDeque<Integer> stk = new ArrayDeque<>();
    static int answer;
    
    void findAndRemove(int move){
        int i=0;
        while(i<board.length && board[i][move-1]==0){
            // System.out.println(board[i][move-1]);
            i++;
        }
        
        
        if(i==board.length) i--;
        
        
        if(board[i][move-1]!=0){
            
            // System.out.println(board[i][move-1]);
            if(stk.size()>0 && stk.peek()==board[i][move-1]){
                // System.out.println(board[i][move-1]);
                stk.pop();
                answer+=2;
            }
            else stk.push(board[i][move-1]); //stack에는 offer 금지!
            
            board[i][move-1]=0; //제거표시
        }
    }
    
    public int solution(int[][] _board, int[] moves) {
        board=_board;
        // System.out.println(Arrays.deepToString(board));
        
        for(int move : moves){
            findAndRemove(move);
        }
        // System.out.println(stk);
        return answer;
    }
}

 

* 풀이2

배열을 스택으로 변경하는 방법

import java.util.*;

class Solution {
    static int[][] board;
    static ArrayDeque<Integer> stk = new ArrayDeque<>();
    static int answer;
    
    
    public int solution(int[][] _board, int[] moves) {
        board=_board;
        // System.out.println(Arrays.deepToString(board));
        
        int n=board.length;
        int m=board[0].length;
        
        ArrayDeque<Integer>[] lanes = new ArrayDeque[m];
        for(int i=0;i<m;++i){
            lanes[i]=new ArrayDeque<>();
        }
        
        for(int j=0;j<m;++j){
            for(int i=n-1;i>=0;--i){
                if(board[i][j]==0) break;
                lanes[j].push(board[i][j]);
            }
        }
        // for(int i=0;i<m;++i){
        //     System.out.println(lanes[i]);
        // }
        
        ArrayDeque<Integer> bucket = new ArrayDeque<>();
        for(int move:moves){
            if(lanes[move-1].isEmpty()) continue;
            int cur = lanes[move-1].pop();
            
            if(bucket.isEmpty()){
                bucket.push(cur);
                continue;
            }
            
            if(bucket.peek()==cur){
                answer+=2;
                bucket.pop();
            }
            else{
                bucket.push(cur);
            }
        }
        
        // System.out.println(bucket);
        
        return answer;
    }
}