[Java] 백준 25556 : 포스택

💻 문제

https://www.acmicpc.net/problem/25556

25556번: 포스택

💻 문제 이해

1. 순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 
2. 순열 A의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
3. 순열 A의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
4. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

• 스택의 특징을 생각해 보면 먼저 넣은 값은 제일 나중에 꺼낼 수 있다. 입력 예제 2번째를 예시로 보자.
• 5 4 3 2 1 이 NO 가 출력이 된다. 그 이유는 제일 큰 숫자가 먼저 입력이 되어 스택에 쌓인다.
• 1이 제일 나중에 들어갔다면 1이 가장 먼저 나올 것이다. 위에 4번에 보면 오른쪽에서 왼쪽으로 나열해야 된다고 적혀있다.
• 즉, 스택에 있는 데이터를 꺼내면 1 -> 2, 1 -> 3, 2, 1 -> 4, 3, 2, 1 -> 5, 4, 3, 2, 1 이렇게 나오므로 문제의 오름차순으로 정렬이 아니다. 그리고 애초에 작성한 코드를 보면 스택 안에 있는 데이터 보다 값이 작으면 4개의 스택 중 다른 스택으로 가서 확인하도록 해놓았다. 모든 스택이 for 문에서 꺼낸 값보다 크다면 멈추도록 설계를 해놓았다. 
• 첫 번째 예시를 보자
• 4 3 6 7 8 9 10 2 1 5라는 값이 입력되었다.
• 4 첫 번째 스택에 저장한다. 3 은 4보다 작으므로 두 번째 스택에 저장한다. 그럼 값이 끝까지 다 들어가면 어떻게 될까.
  첫 번째 스택 : 4 6 7 8 9 10
  두 번째 스택 : 3 5
  세 번째 스택 : 2
  네 번째 스택 : 1
• 이렇게 모든 값을 꺼냈을 때 오름차순으로 꺼내지는 것을 확인할 수 있다.

💻 소스코드

package baekjoon;

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

public class B25556 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> numbers = new ArrayList<>();

        for (int i = 0; i < n; i++) { // n 만큼 숫자를 입력해서 numbers 에 저장한다.
            numbers.add(Integer.parseInt(scanner.next()));
        }

        List<Stack<Integer>> stackList = new ArrayList<>();

        for (int i = 0; i < 4; i++) { // 1 부터 시작이므로 0을 미리 저장한다.
            stackList.add(new Stack<>());
            stackList.get(i).push(0);
        }

        boolean isFlag = true;
        for (int number : numbers) {
            boolean isNumber = false;
            for (Stack<Integer> integers : stackList) {
                if (number > integers.peek()) { // 리스트 안에 스택 한개를 꺼내서 맨위의 값을 꺼냈을 때 스택에 있는애보다 크면 스택에 저장
                    integers.push(number);
                    isNumber = true; // number 가 더 크면 true 하고 멈추기
                    break;
                }
            }

            if (!isNumber) { // 숫자가 작거나 같아서 true 로 바뀌지 않았다면 제일 밖에 for 문 정지
                isFlag = false;
                break;
            }
        }
        if (isFlag) { // 모든 숫자들을 스택에 저장할 수 있었으면 YES 그렇지 않으면 NO
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

}