[Java] 백준 25556 포스택

[Java] 백준 25556 포스택

 

풀이

랜덤으로 되어있는 순열을, 4개의 스택을 이용해서 오름차순으로 정렬을 하는 것이다

 

여기서 중요한 것은 각 모든 스택은 오름차순으로 나열이 되어 있어야 한다

• 이유는, 제일 큰 수를 오른쪽부터 왼쪽으로 숫자가 1씩 떨어지면서 정렬을 해야 하는 상황이다
• 그래서 만약에 스택에 모든 숫자를 넣을 수 있다면, 오름차순으로 정렬이 가능하다
• 반대로 스택에 숫자 하나라도 못 넣으면, 정렬이 불가능해진다

 

코드를 보게 되면, 스텍에 값들을 넣었지, 빼는 것은 생략했다

import java.util.Stack;
import java.util.Scanner;
import java.util.ArrayList;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        Stack<Integer> stack3 = new Stack<Integer>();
        Stack<Integer> stack4 = new Stack<Integer>();

        int n = scanner.nextInt();
        ArrayList <Integer> list = new ArrayList<Integer> ();

        for (int i = 0 ; i < n ; i ++) {
            list.add(Integer.parseInt(scanner.next()));
        }

        boolean isPossible = true;
        for (int num : list) {
            if (stack1.empty() || stack1.peek() < num) {
                stack1.push(num);
            } else if (stack2.empty() || stack2.peek() < num) {
                stack2.push(num);
            } else if (stack3.empty() || stack3.peek() < num) {
                stack3.push(num);
            } else if (stack4.empty() || stack4.peek() < num) {
                stack4.push(num);
            } else {
                isPossible = false;
                System.out.println("NO");
                break;
            }
        }

        if (isPossible) {
            System.out.println("YES");
        }
    }
}