[BOJ 25556] 포스택
- 문제풀이
문제
포닉스는 길이가 $N$인 순열 $A$와 네 개의 비어 있는 스택을 가지고 있다.
- 길이가 $N$인 순열이란, $1$ 이상 $N$ 이하의 서로 다른 정수 $N$개가 임의로 나열된 수열을 말한다.
- 스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다.
포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.
순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 $1, 2, 3, \cdots N$으로 만들어야 한다.
- 순열 $A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
- 순열 $A$의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
- 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.
포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.
입력
첫째 줄에 순열의 길이 $N$이 주어진다. $(1 ≤ N ≤ 100\,000)$
둘째 줄에 순열 $A$의 원소 $A_i$가 공백으로 구분되어 주어진다. 모든 $A_i$는 $1$ 이상 $N$ 이하의 서로 다른 정수임이 보장된다.
출력
포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 1024MB |
풀이
길이가 $N$인 순열을 4개의 스택을 이용해 오름차순으로 정렬할 수 있는지 판별하는 문제다. 문제의 조건에 따르면 스택에서 원소를 꺼내 오른쪽에서 왼쪽으로 나열했을 때 $1, 2, 3, \dots, N$이 되어야 하므로, 스택에서 나오는 순서는 $N, N-1, \dots, 1$인 내림차순이어야 한다.
스택은 후입선출(LIFO) 구조이므로, 내림차순으로 원소를 꺼내기 위해서는 스택 내부의 데이터가 아래에서부터 위로 갈수록 커지는 오름차순으로 쌓여 있어야 한다. 따라서 순열의 원소를 차례대로 네 개의 스택 중 하나에 넣을 때, 해당 스택의 가장 위에 있는 값보다 넣으려는 값이 더 커야만 정렬 상태를 유지할 수 있다.
해결 방법은 다음과 같다:
- 4개의 스택의 현재 최상단 원소 상태를 저장할 배열을 준비한다.
- 순열의 원소를 하나씩 읽으며, 4개의 스택 중 현재 최상단 원소가 새 원소보다 작은 스택이 있는지 확인한다.
- 만약 새 원소보다 작은 값을 가진 스택이 여러 개라면, 그중 가장 큰 값을 가진 스택에 넣는 것이 유리하다. 소스 코드에서는 이처럼 새 원소보다 작으면서 가장 큰 값을 가진 스택을 찾는 그리디 알고리즘 방식을 사용한다.
- 만약 4개의 스택 모두 최상단 원소가 새 원소보다 크다면, 어떤 스택에 넣더라도 오름차순 유지가 불가능하므로 청소가 불가능한 상태(
NO)가 된다. - 모든 원소를 성공적으로 스택에 분배했다면
YES를 출력한다.
이 알고리즘의 시간 복잡도는 순열의 길이 $N$에 대해 다음과 같다:
\[O(N)\]순열의 최대 길이가 $100\,000$이므로 제한 시간 1초 내에 충분히 해결 가능하다.
소스코드
Github Link : Source Code