포스택

* 스택이란

· 메모리의 스택 영역은 함수의 호출과 관계되는 지역변수, 매개변수, 리턴 값등의 임시데이터를 저장한다.

· 스택이란 단어는 ‘차곡 차곡 쌓여진 더미’를 의미한다.

· LIFO(Last In First Out, 후입선출) 구조라고도 한다.

*  스택의 구조 이해하기 

   가장 먼저 저장되는 데이터는 스택의 아래 쪽(높은 주소)부터 쌓이고, 다음 저장되는 데이터가 바로 그 위(낮은 주소)에 쌓인다.

 

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

public class stack {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();  // stack의 길이
        int[] arrA = new int[N];  // 길이가 N인 순열 A

        for (int i = 0; i < N; i++) {
            arrA[i] = sc.nextInt(); // N만큼 순열 A에 정수 배치
        }

        Stack<Integer>[] stackA = new Stack[4]; // error prevent
        for(int i = 0; i < 4; i++){
            stackA[i] = new Stack<>();
            stackA[i].push(0);
        }

        boolean can = true;
        for (int num : arrA){ // 4 3 6 7 8 9 10 2 1 5
            boolean cant = false;
            for (int i = 0; i < 4; i++) {
                if(num > stackA[i].peek()){ // 현재 넣으려는 값이 A 가장 윗 값 보다 크다면 배치, 작다면 다음 stack으로
                    stackA[i].push(num); // 배치
                    cant = true; // 성공
                    break;
                }
            }
            if(!cant){
                can = false;
                break;
            }
        }
        if(can == true){
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
    }
}

요번에 풀어본 알고리즘 문제는 stack 구조에 대해서도 처음이여서 그런지 348분이 소요되었다.(WTF)