C++에서 배열이 스택 정렬 가능한지 확인하는 방법

1부터 n까지의 서로 다른 고유한 원소로 구성된 배열 nums가 있다고 가정해 보겠습니다. 이 배열의 원소들을 임시 스택 하나를 거쳐 다른 배열에 옮겨 담을 때, 결과 배열이 정렬된 상태가 될 수 있다면 그 배열은 스택 정렬 가능(stack sortable)하다고 말합니다. 이 글에서는 C++로 주어진 배열이 스택 정렬 가능한지 판별하는 방법을 알아보겠습니다.

사용할 수 있는 연산

스택 정렬 가능 여부를 확인할 때는 아래 두 가지 연산만 사용할 수 있습니다.

배열 → 스택: 배열의 맨 앞 원소를 삭제하고, 그 원소를 스택에 push합니다.
스택 → 결과 배열: 스택의 최상단(top) 원소를 삭제(pop)하고, 결과 배열의 맨 끝에 삽입합니다.

주어진 배열의 모든 원소가 위 연산만으로 결과 배열에 옮겨졌을 때, 결과 배열이 비내림차순(non-decreasing order)으로 정렬되어 있다면 주어진 배열은 스택 정렬 가능한 것입니다.

예시

입력이 nums = [8, 6, 5, 3, 1]라고 해보겠습니다. 각 원소를 차례대로 스택에 쌓은 후 위쪽부터 하나씩 꺼내면 [1, 3, 5, 6, 8]과 같이 정렬된 배열을 만들 수 있습니다. 따라서 이 배열은 스택 정렬 가능하며 출력은 True가 됩니다.

해결 알고리즘

다음 단계를 따라 문제를 해결할 수 있습니다.

스택 stk를 하나 선언하고, 결과 배열에 마지막으로 채운 값을 저장할 변수 last를 0으로 초기화합니다.
i를 0부터 배열 v의 크기 미만까지 1씩 증가시키며 다음을 반복합니다.
- 스택이 비어 있지 않다면:
  - top을 스택의 최상단 원소로 설정합니다.
  - top이 last + 1과 같은 동안 다음을 반복합니다.
    - last를 1 증가시키고 스택에서 pop합니다.
    - 스택이 비어 있으면 반복문을 빠져나갑니다.
    - 그렇지 않으면 top을 다시 스택의 최상단 원소로 갱신합니다.
  - 스택이 비어 있으면 v[i]를 스택에 push합니다.
  - 스택이 비어 있지 않으면 top과 v[i]를 비교합니다.
    - v[i]가 top보다 작으면 v[i]를 push합니다.
    - 그렇지 않으면 false를 반환합니다. (스택 정렬 불가능)
- 스택이 비어 있으면 v[i]를 그대로 push합니다.
모든 원소를 처리한 후 true를 반환합니다.

동작 원리

결과 배열에는 반드시 1, 2, 3, … 순서로 값이 채워져야 합니다. 따라서 스택의 top이 다음에 나와야 할 값(last + 1)과 일치한다면 즉시 pop하는 것이 항상 유리합니다. 반면, 새로 들어올 원소가 스택의 top보다 크다면 그 아래에 남아 있는 더 작은 값들은 나중에도 결코 먼저 꺼낼 수 없으므로 정렬이 불가능합니다. 이 두 가지 규칙만 지키면 O(n) 시간 복잡도로 스택 정렬 가능 여부를 판별할 수 있습니다.

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> &v) {
    stack<int> stk;
    int last = 0;
    for (int i = 0; i < v.size(); i++) {
        if (!stk.empty()){
            int top = stk.top();
            while (top == last + 1) {
                last = last + 1;
                stk.pop();
                if (stk.empty()){
                    break;
                } top = stk.top();
            }
            if (stk.empty()) {
                stk.push(v[i]);
            }else{
                top = stk.top();
                if (v[i] < top){
                    stk.push(v[i]);
                }else{
                    return false;
                }
            }
        }else{
            stk.push(v[i]);
        }
    } return true;
}
main(){
    vector<int>
    v = {8, 6, 5, 3, 1};
    cout << solve(v);
}

입력

{8, 6, 5, 3, 1}