백준 25556번: 포스택 문제

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

25556번: 포스택

 

입력 예시 1)

10
4 3 6 7 8 9 10 2 1 5  --> YES

입력 예시 2)

5
5 4 3 2 1  --> NO

나의 해결법 생각 : 앞에 들어온 숫자 > 뒤에 들어온 숫자일 때 cnt(=0)가 하나씩 증가하여 cnt 가 3보다 클 경우 문제에서 제시하는 순열을 청소할 수 없다고 생각함

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int cnt = 0;
        int init = Integer.parseInt(st.nextToken());
        while (st.hasMoreTokens()) {
            int second = Integer.parseInt(st.nextToken());
                if (init > second ) {
                    cnt++;
                }
            init = second;
        }
        if (cnt > 3) {
            System.out.print("NO");
        }else{
            System.out.print("YES");
        }
    }
}

정답 해결법 -> 모든 스택에서 입력받은 숫자가 클 경우 cnt 증가 -> 오름차순으로 정리가 가능한가?

 

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer>[] stack= new Stack[4];
        for (int i = 0; i < 4; i++) {
            stack[i] = new Stack<>();
            stack[i].push(0);
        }

        while (st.hasMoreTokens()) {
            int second = Integer.parseInt(st.nextToken());
            int cnt = 0;
            for (int i = 0; i < 4; i++) {
                if (stack[i].peek() < second) {
                    stack[i].push(second);
                    break;
                }else{
                    cnt++;
                }
                if (cnt > 3) {
                    System.out.print("NO");
                    return;
                }
            }
        }
        System.out.print("YES");

    }
}