스택(stack)은 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO:Last In First Out)이다. 즉, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.
스택에 데이터를 넣는 작업을 푸시(push)라고하고 꺼내는 것을 팝(pop)이라고 한다.
또, 푸시와 팝이 이루어지는 쪽을 탑(top)이라하고, 그 반대쪽인 스택의 가장 아랫부분을 바텀(bottom)이라고 한다.
피크(peek) 메소드는, 스택의 최상위 요소를 반환하지만, 제거하지는 않는다.
따라서 스택의 최상위 요소를 확인할 때 유용하게 사용된다.
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int top = stack.peek(); // top = 3
출처 : java2blog.com
포닉스는 길이가 N인 순열 A와 네 개의 비어 있는 스택을 가지고 있다.
포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.
순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 1, 2, 3, ..., N으로 만들어야 한다.
포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.
첫째 줄에 순열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 순열 A의 원소들은 공백으로 구분되어 주어진다.
모든 원소들은 1 이상 N 이하의 서로 다른 정수임이 보장된다.
포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.
10
4 3 6 7 8 9 10 2 1 5
예제 출력 1
YES
5
5 4 3 2 1
예제 출력 2
NO
import java.util.Scanner;
import java.util.Stack;
public class Mian {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정수 N 입력받기
// N을 통해 배열 만들기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
//스택 만들기 4개
Stack<Integer>[] stacks = new Stack[4];
for (int i = 0; i < 4; i++) {
stacks[i] = new Stack<>();
stacks[i].push(0); // 모든스택에 0
}
for (int i = 0; i <n; i++) {
boolean push = false;
for (int j = 0; j <4; j++) {
if(stacks[j].peek()<arr[i]){
stacks[j].push(arr[i]);
push = true;
break;
}
}
if(!push){
System.out.println("NO");
return; // 나가기
}
}
System.out.println("YES");
}
}