1. 길이가 N인 순열과 4개의 비어 있는 스택이 있다.
2. 순열의 원소들을 앞에서부터 순서대로 네 개의 스택 중 하나에 삽입한다.
3. 순열의 모든 원소를 스택에 삽입했다면, 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
4. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다
순열을 1, 2, 3, ..., N으로 만들 수 있는지 여부를 판별해야 한다.
예제 입력 1
10
4 3 6 7 8 9 10 2 1 5- 입력받은 숫자의 순서는 4, 3, 6, 7, 8, 9, 10, 2, 1, 5 이다
- 스택에 숫자를 삽입하는 규칙은 해당 숫자가 스택의 최상단 숫자보다 클 경우에만 가능하다.
- (numbers.get(i) > stacks.get(i).peek())
- 숫자는 스택에 앞에서부터 차례대로 삽입되며, 숫자는 네 개의 스택 중 하나에만 삽입될 수 있다.
이 경우에는
첫 번째 스택 - 4 6 7 8 9 10
두 번째 스택 - 3 5
세 번째 스택 - 2
네 번째 스택 - 1
이렇게 하면 모든 숫자를 스택에 삽입할 수 있다.
예제 입력 2
5
5 4 3 2 1
모든 숫자가 내림차순이므로
5
4
3
2
이런식으로 삽입이 되서 1이 들어갈 자리가 없기 때문에 안된다
예제 코드
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Baejoon25556 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //입력 받기
int n = sc.nextInt(); // 순열의 길이 입력
List<Integer> numbers = new ArrayList<>(); //순열을 저장할 ArrayList 생성
for (int i = 0; i < n; i++) {
numbers.add(Integer.parseInt(sc.next())); //순열의 각 요소 입력받기
}
List<Stack<Integer>> stacks = new ArrayList<>(); //4개의 스택을 저장할 스택리스트
for (int i = 0; i < 4; i++) {
Stack<Integer> stack = new Stack<>(); //각 스택 생성
stack.push(0); //초기값 0 설정
stacks.add(stack); //ArrayList에 스택 추가
}
outer: // 라벨을 지정해서 특정 루프를 나갈 수 있게 한다
for (int i = 0; i < numbers.size(); i++) { //순열의 개수만큼 반복
for (int j = 0; j < stacks.size(); j++) { //4개의 스택에 각 스택마다
if (numbers.get(i) > stacks.get(j).peek()) { //현재 숫자가 스택의 가장 위 숫자보다 크면
stacks.get(j).push(numbers.get(i)); // 스택에 현재 숫자를 넣는다
continue outer; //다음 숫자로 이동
}
}
System.out.println("NO");
return;
}
System.out.println("YES");
}
}
