[25556] 포스택

문제 링크 : https://www.acmicpc.net/problem/25556

25556 - 포스택

본문

포닉스는 길이가 $N$인 순열 $A$와 네 개의 비어 있는 스택을 가지고 있다.

• 길이가 $N$인 순열이란, $1$ 이상 $N$ 이하의 서로 다른 정수 $N$개가 임의로 나열된 수열을 말한다.
• 스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다.

포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.

순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 $1, 2, 3, \cdots N$으로 만들어야 한다.

1. 순열 $A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
2. 순열 $A$의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
3. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

입력

첫째 줄에 순열의 길이 $N$이 주어진다. $(1 ≤ N ≤ 100\,000)$ 

둘째 줄에 순열 $A$의 원소 $A_i$가 공백으로 구분되어 주어진다. 모든 $A_i$는 $1$ 이상 $N$ 이하의 서로 다른 정수임이 보장된다.

출력

포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.

제한

시간 제한	메모리 제한
1sec	1024MB

---

풀이

문제 이해부터 해보도록 하자. 절차를 보면, 수를 스택에 넣고, 그 스택에서 수를 꺼내서 오른쪽부터 둔다고 한다. 스택에서 꺼낸 수들은 정렬되어있어야하므로, 오른쪽에는 큰 수가 와야 한다는 것을 알 수 있다. 그렇다면 스택에서는 큰 수인 순서대로 뽑아야 한다는 것이고, 스택에 수를 넣을 때도 수가 큰 순서대로 오른쪽에 존재해야함을 알 수 있다.

결국 문제를 해결하기 위해서는 모든 스택이 오름차순이 되도록 수를 넣어야함을 알 수 있다. 수를 넣을 때 스택이 오름차순이 되도록 스택의 가장 마지막 원소들만 확인하고 넣으려는 수보다 작을 때만 스택에 수를 넣어 스택이 항상 오름차순이 되도록 하면 된다. 스택이 4개이므로 어떤 스택에 수를 넣는 것이 좋을지 정하는 것이 관건인데, 생각해보면 의외로 간단하다.

스택이 2개 있고, 각 스택의 마지막에는 $4$, $6$이 있다고 해보자. 그리고 우리는 $7$, $5$를 순서대로 넣을 예정이다. $7$은 어느 곳에나 넣어도 스택들은 오름차순을 유지할 수 있다. 다만 1번 스택에 $7$을 넣게 되면 다음 $5$는 어느 곳에도 넣을 수 없게 된다. 하지만 2번 스택에 $7$을 넣는다면 $5$을 1번 스택에 넣음으로써 모든 스택을 오름차순으로 유지할 수 있다. 결론은, 더 많은 가능성을 가진 스택을 보존할 수 있도록 마지막 원소가 넣으려는 수보다 크지 않으면서 가장 큰 스택을 선택해서 넣어주면 된다. 그런 스택이 없다면 (넣으려는 원소가 모든 스택의 마지막 원소보다 작다면) 정렬이 불가능한 순열임을 알 수 있다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2024 / 4 / 12

#include <stdio.h>

#define NUMBER_OF_STACK 4
const int NONE = -1;
const int ZERO = 0;

int n;
int stack[NUMBER_OF_STACK];

#define max(a, b) (((a) > (b)) ? (a) : (b))
int main() {
    scanf("%d", &n);
    for (int i = 0; i < NUMBER_OF_STACK; ++i) {
        stack[i] = ZERO;
    }

    for (int i = 0; i < n; ++i) {
        int input;
        scanf("%d", &input);

        int idx = NONE, temp = NONE;
        for (int j = 0; j < NUMBER_OF_STACK; ++j) {
            if (temp < stack[j] && stack[j] < input) {
                idx = j, temp = stack[j];
            }
        }

        if (idx == NONE) {
            printf("NO");
            return 0;
        } else {
            stack[idx] = input;
        }
    }

    printf("YES");
    return 0;
}