백준 25556번

<문제>
https://www.acmicpc.net/problem/25556

<내가 생각한 문제 풀이>
예제를 보면 4 3 6 7 8 9 10 2 1 5 오름 차순 으로 나타내려면 Stack이 각각 필요하다.
각각 필요하다는 의미는 4 보다 큰 수가 와야 하는데 다음이 3이 오게되면 오름차순으로 나타낼 수 없을 것이다. 그래서 3을 따로 담을 수 있는 Stack을 하나 더 필요하다.
pop과 push 그리고 peek을 잘 활용해 볼 필요가 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class 포스택25556 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        //비교를 위한 가장 작은 수를 각 스택에 삽입한다.
        Stack<Integer>[] stacks = new Stack[4];
        for(int i=0; i<4; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0);
        }

        //스택의 peek보다 큰 수라면 삽입하기
        for(int i=0; i<n; i++) {
            boolean flag = false;
            for(int j=0; j<4; j++) {
                if(stacks[j].peek() < arr[i]) {
                    stacks[j].push(arr[i]);
                    flag = true;
                    break;
                }
            }

            //모든 스택에 삽입하지 못 했다면
            if(!flag) {
                System.out.println("NO");
                return;
            }
        }

        //순열 청소가 완료되면
        System.out.println("YES");

    }
}

다른 풀이가 있나 봤는데 좀 다른 풀이가 있어 이거는 직접 짜보지는 못했고 따라치면서 의미를 파악하려고 노력했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main25556 {
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        Stack[] stacks = new Stack[4];

        for (int i = 0; i < 4; i++)
            stacks[i] = new Stack<>();
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int[] arr = new int[num];
        int idx = 0;

        while (stk.hasMoreTokens()) {
            arr[idx++] = Integer.parseInt(stk.nextToken());

            for (int i = 0; i < num; i++) {
                int target = arr[i]; //이번 순서 순열
                boolean flag = false;
                for (int j = 0; j < 4; j++) {
                    if (stacks[j].isEmpty()) { // 스택 비었을 때 넣기
                        flag = push(stacks[j], target);
                        break;
                    }

                    Integer peek = (Integer) stacks[j].peek();
                    if (target > peek){ //이번 순서 순열이 스택에 최상단 보다 크다면 넣기
                        flag = push(stacks[j], target);
                        break;
                    }
                }

                if (!flag) {
                    System.out.println("NO");
                    return;
                }
            }
            System.out.println("YES");
        }
    }

    public  boolean push(Stack stack, int target) {
        boolean flage = true;
        stack.push(target);
        return flage;
    }

    public static void main(String[] args) throws IOException {
        new Main25556().solution();
    }
}