[Coding/Backjoon] 25556번 포스택

 

 

 

 

 

 

 

 

 

 

1. 구현할 방식

4개의 스택에 순열을 차례대로 넣는다. 이때 먼저 들어간 데이터보다 크면 해당 스택에 데이터가 들어가고 만약 작다면 그 다음 스택에 데이터를 집어넣는다.

이때 4개의 스택에 모두 들어가지 못한 n번째 데이터의 인덱스값에 true 를 넣어준다. 만약 스택에 데이터 삽입이 끝나고 ture / false 배열에서 true 가 존재한다면 순열을 정렬하지 못한 것이다.

 

2. 코드 

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

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

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt(); //순열의 길이

        ArrayList<Integer> numList = new ArrayList<Integer>();  //주어진 순열을 담을 배열 생성

        for (int i = 0; i < num; i++) {
            numList.add(sc.nextInt());
        }

        ArrayList<Stack<Integer>> stackList = new ArrayList<>();  //Stack을 담을 배열 생성

        for (int i = 0; i < 4; i++) { //4개의 스택을 배열로 생성
            stackList.add(new Stack<Integer>());
            stackList.get(i).add(0);  //각각의 스택에 0을 push
        }

        boolean[] pushPossible = new boolean[num];

        for (int i = 0; i < num; i++) {
            for (int j = 0; j < 4; j++) {
                if (numList.get(i) > stackList.get(j).peek()) {
                    stackList.get(j).add(numList.get(i));
                    pushPossible[i] = false;
                    break;
                }
                pushPossible[i] = true;  //Stack 에 값이 삽입되지 못했다면 그 값의 인덱스에 해당하는 값은 true로 표기
            }
        }


        for (int i = 0; i < num; i++) {
            if (pushPossible[i] == true) { //Stack에 들어가지 못한 데이터가 있다면
                System.out.println("NO");
                break;
            }

            if (i == num - 1) { //순열의 마지막 값일 때
                if (pushPossible[i] == true) { //Stack 에 들어가지 못했다면
                    System.out.println("NO");
                }

                System.out.println("YES"); //마지막 값까지 Stack에 들어갔다면
            }
        }
    }
}