단조 스택과 단조 큐(Monotone Stack & Queue)

🔍 단조 스택과 단조 큐(Monotone Stack & Queue)

단조 스택과 단조 큐는 기본적인 스택과 큐에 들어가는 데이터들이 단조 증가 혹은 단조 감소를 유지하도록 하는 것을 말합니다. 단조 증가는 모든 데이터가 순차적으로 a1 ≤ a2를 유지하는 것을 의미하고, 단조 감소는 모든 데이터가 순차적으로 a1 ≥ a2를 유지하는 것을 의미합니다.

무엇을 할 수 있나?

• 특정 원소 a보다 왼쪽에 있는 원소들 중 처음으로 나타나는 a미만의 원소의 위치 찾기(O(n))

어떻게 구현할 수 있나?

단조 스택과 단조 큐의 구현 자체가 까다로운 것은 아닙니다! 이를 이해한 뒤에 단조 스택과 단조 큐를 써야하는 문제에서 적절히 잘 사용할 수 있도록 연습하고 익숙해지는 것이 조금 더 중요할 것 같습니다.

• 단조 스택

먼저 단조 스택부터 데이터들이 단조 증가를 유지한다고 가정하고 동작 방식을 살펴보겠습니다.

다음과 같은 수열이 순서대로 스택에 들어올 때,

5 3 2 6 9 4 10 

다음 순서를 보면서 스택이 어떻게 데이터의 단조 증가를 유지시키는 지 확인해보시기 바랍니다.

1. [ 5(top) ]

2. [ 3(top) ] (단조 증가가 깨지므로 pop 후 push 3)

3. [ 2(top) ] (단조 증가가 깨지므로 pop 후 push 2)

4. [ 2 6(top) ]

5. [ 2 6 9(top) ]

6. [ 2 4(top) ] (단조 증가가 깨지므로 pop 후 push 4)

7. [ 2 4 10(top) ]

즉, 어떠한 스택이 단조 스택이 되기 위해서는 스택에 새로 push되는 값보다 top이 클(단조 증가의 경우) 동안 pop을 시킨 후 새로운 값을 push하는 것을 알 수 있습니다. 물론 단조 감소의 경우 top이 새로 들어오는 값보다 작을 동안 pop을 한 후 push하면 됩니다.

• 단조 큐

이번에는 단조 큐가 데이터의 단조 증가를 유지하면서 위의 동일한 입력을 어떻게 처리하는지 살펴보겠습니다. 단조 큐의 경우는 일반적인 큐가 아닌 덱(Deque)을 이용하여 구현합니다.

1. [ 5(back) ]

2. [ 3(back) ] (단조 증가가 깨지므로 pop_back 후 push 3)

3. [ 2(back) ] (단조 증가가 깨지므로 pop_back 후 push 2)

4. [ 2 6(back) ]

5. [ 2 6 9(back) ]

6. [ 2 4(back) ] (단조 증가가 깨지므로 pop_back 후 push 4)

7. [ 2 4 10(back) ]

잠깐! 이럴꺼면 왜 스택과 큐를 분리한걸까?

맞습니다. 단순히 단조 증가/감소를 유지하는데는 둘 중 하나로만 구현을 해도 충분한 것 같아 보입니다. 여기서 위에서 언급한 "이해한 뒤에 단조 스택과 단조 큐를 써야하는 문제에서 적절히 잘 사용"을 다시 생각해보아야 합니다.

문제의 요구 사항(예를 들면 단조 증가가 특정 인덱스 크기 범위 내에서 이루어지도록 하는 등)에 따라 큐만으로는 구현이 어려울 수가 있습니다. 이러한 경우 덱을 활용하여 상황에 따라 pop_back도 시켜가며 데이터의 단조 증가/감소를 유지시켜야 합니다.

아래의 코드를 살펴보시면 단조 스택과 단조 큐의 구현은 그리 까다롭지 않다는 것을 알 수 있습니다. 따라서 문제 해결을 위해 단조 스택 또는 단조 큐를 사용해야 한다는 것을 깨닫고 난 후에 문제의 조건을 만족시키기 위해 어떤 것을 선택하여 구현할 지가 중요하겠습니다.

⌨️ C++ 구현 코드

#include <bits/stdc++.h>

using namespace std;

int main()
{
    stack<int> ms;
    deque<int> mq;
    int nums[10] = {2,5,3,7,9,8,6,1,0,4};

    //단조 스택(데이터가 단조 증가하는 경우)
    for(int i=0;i<10;i++){
        while(!ms.empty() && ms.top() > nums[i]){
            ms.pop();
        }
        ms.push(nums[i]);
    }

    //단조 큐(데이터가 단조 증가하는 경우)
    for(int i=0;i<10;i++){
        while(!mq.empty() && mq.back() > nums[i]){
            mq.pop_back();
        }
        mq.push_back(nums[i]);
    }
}

📚 참고 문헌

SSU-SCCC-Study 2022-winter-intermediate ― Monotone Stack/Queue

JusticeHui가 PS하는 블로그 ― monotone stack