백준 25556 포스택 문제풀이

문제 링크 : https://www.acmicpc.net/problem/25556

사용 자료구조 : 스택

문제 자체에 스택을 사용한다는 말이 있어서 스택을 사용하여 풀기로 했다.

찾아낸 규칙

일단 스택에 규칙에 맞게 들어가기만 한다면 다시 출력할 수 있음은 보장 된다! 즉, 배열의 모든 수가 스택 4개에 들어갈 수 있다면 오름차순으로 출력이 가능하게 된다는 말이다!

따라서 규칙만 생각해 보면 됐는데, 규칙은 손으로 그림을 그려가며 파악해봤다.
스택의 top보다 큰수가 스택에 push되어야 한다는 것을 알게되었다.

코드설명

배열의 각 수마다 4개의 스택을 차례대로 살펴보게 된다. 만약 살펴보는 스택이 비어 있다면 아직 아무런 수도 들어가지 않았으므로 배열의 수를 스택에 넣고 flag를 true로 설정하고 다음 숫자로 넘어간다.

반면, 비어있지 않다면 스택의 맨위 숫자를 살펴본다. 배열의 숫자가 peek한 숫자보다 크다면 스택에 집어 넣고 flag를 true로 설정하고 다음 숫자로 넘어간다. 만약 배열의 숫자가 4개의 스택에서 peek한 숫자보다 작다면 어떠한 스택에도 들어갈 수 없다. 따라서 스택에 들어갈 수 없는 숫자가 생기므로 flag는 false가 된다.

각 숫자마다 스택에 넣었는지 아닌지를 flag를 통해 확인한다. 스택에 넣지 못했다(flag가 false)면 스택에 들어가지 않는 숫자가 생기는 것이므로 NO를 출력하고 리턴한다.

각 숫자를 도는 중간에 NO출력하고 리턴하지 않고, 모든 숫자를 돌았으면 스택에 모든 숫자가 들어간 것이므로 YES를 출력하고 리턴한다.

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

// 스택의 top보다는 큰 수를 stack에 넣는다.
public class Main {
    public void solution(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack[] stacks = new Stack[4]; // 4개의 스택
        for(int i = 0; i<4; i++)
            stacks[i] = new Stack<Integer>(); // 스택 4개 생성

        int [] arr = new int[n];
        int idx = 0;

        while(idx != n)
            arr[idx++] = sc.nextInt();

        for (int i = 0; i < n; i++) {
            int target = arr[i];
            boolean flag = false;
            for(int j = 0; j<4; j++){
                if (stacks[j].isEmpty()) {
                    flag = true;
                    stacks[j].push(target);
                    break;
                }
                Integer peek = (Integer) stacks[j].peek();
                if (target > peek) {
                    flag = true;
                    stacks[j].push(target);
                    break;
                }
            }
            if (!flag) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }


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

}