[Java] 백준 25556번 포스택 문제풀이

stack의 특성인 후입선출(Last In First Out, LIFO)을 이용한 문제다.
문제의 기준으로 순열을 청소하기 위해서는 4개의 스택에서 숫자를 꺼낼 때 큰 숫자를 먼저 꺼내야 하며, 이에 따라 각 스택에 오름차순으로 스택을 넣으면 된다.

로직은 다음과 같다.

예제입력인

4 3 6 7 8 9 10 2 1 5 

을 넣는다고 할 때

왼쪽의 스택부터 하나씩 차례대로 반복하여 보면서
현재 넣어야 하는 수 n 이 해당하는 스택에 들어있는 수보다 크다면 그 스택에 n을 push한다.

처음 숫자 4는 첫 스택이 비어있으므로

 4
___ ___ ___ ___

다음숫자 3은 첫 스택의 최상단 숫자 4보다 작으므로 다음스택을 확인하고, 넣을 수 있으므로

 4   3
___ ___ ___ ___

이 된다.

다음 숫자들은 연속해서 큰 숫자이므로 중간생략한다면

 10
 9
 8
 7
 6
 4   3
___ ___ ___ ___

다음숫자 2는

 10
 9
 8
 7
 6
 4   3   2
___ ___ ___ ___

이렇게 반복하여 오름차순으로 숫자를 넣게된다면

 10
 9
 8
 7
 6   5
 4   3   2   1
___ ___ ___ ___

이런 구조의 스택이 완성되며, 숫자를 순서대로 꺼낼 수 있게 되어 YES를 출력한다.

이러한 로직을 코드로 구현하면 다음과 같다.

import java.util.Arrays;
import java.util.Stack;
import java.util.Scanner;

public class FourStack {
    static Stack<Integer> s1 = new Stack<>();
    static Stack<Integer> s2 = new Stack<>();
    static Stack<Integer> s3 = new Stack<>();
    static Stack<Integer> s4 = new Stack<>();

    static String makeStack(int[] arr, Stack[] stackArr){

        for(int i = 0 ; i < arr.length ; i++){

            int num = arr[i];

            for(Stack st: stackArr){

                if((int)st.peek() < num){

                    st.push(num);
                    num = 0;
                    break;

                }

            }// stack 의 최상단 숫자보다 현재숫자가 더 크다면 넣음

            if(num != 0) return "NO";// 현재숫자가 어느 스택에도 들어가지 못한다면 NO return

        }// 입력받은 숫자만큼 반복

        return "YES";// 모든 숫자가 스택에 들어가 for문이 끝나면 YES return

    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        scan.nextLine();

        int[] arr = Arrays.stream(scan.nextLine().split(" ")).
                mapToInt(Integer::parseInt).toArray();

        Stack[] stackArr = {s1, s2, s3, s4};

        for(Stack st: stackArr){

            st.push(-1); // 스택에 isEmpty를 체크하는 것 대신 -1을 넣어 바로 넣을 수 있게 함

        }

        System.out.println(makeStack(arr, stackArr));
    }
}