알고리즘 - 단조 스택 (Monotonic Stack)

단조 스택 (Monotonic Stack)

단조 스택이란, Stack을 활용한 알고리즘중 하나이다.

수학에서 단조란, 우상향 혹은 우하향을 계속 유지하는 형태를 의미한다.

 

단조 스택도 이와 유사하다.

스택 내부의 원소가 오름차순 혹은 내림차순으로 정렬된 형태를 유지하는 것을 의미한다.

 

그렇다면, 단조 스택을 어떻게 활용할까?

단조 스택은 보통 NGE 혹은 PGE를 구하기 위해 사용한다.

 

NGE, PGE

NGE는 Next Greater Element의 약자로, 다음의 수중 가장 가까운 더 큰 수를 의미한다.

PGE는 Previous Greater Element의 약자로, 이전의 수중 가장 가까운 더 큰 수를 의미한다.

 

말로만 보면 이해가 잘 안된다.

아래 예시를 보자.

 

만약, 배열에 {1, 7, 5, 3, 6, 10} 이 있다고 해보자.

 

5 기준으로 보았을 때, 뒤의 원소는 3, 6, 10이 있다.

이 중 5보다 더 큰 원소는 6과 10이 있다.

6이 5와 가장 가깝기 때문에, 6이 5의 NGE가 된다.

 

3을 기준으로 보았을 때, 앞의 원소는 1, 7, 5가 있다.

이 중 3보다 더 큰 원소는 7과 5가 있다.

5가 3과 가장 가깝기 때문에, 5가 3의 PGE가 된다.

 

구현 방법

먼저, 기대값을 보고 가자.

 

1,7,5,3,6,10 이라는 배열이 처음에 주어진다면, NGE와 PGE는 그림과 같을 것이다.

X표시된 부분은 해당 원소에 대해 NGE혹은 PGE가 존재하지 않는다는 뜻이다.

 

본인보다 더 큰 수가 범위내에 없다면, X를 표시한 것이다.

 

이제, 차례대로 배열 원소들의 NGE를 구해본 뒤, 기대값과 동일한지 확인해보자.

 

먼저, 사용할 스택을 하나 선언해주었고, NGE를 저장할 Answer배열도 선언해주었다.

먼저, 배열의 마지막 원소를 Stack에 넣어보자.

Stack에는 10이라는 값이 삽입되었고, 해당 원소는 배열의 마지막 원소라 NGE가 존재하지 않으므로 Answer엔 -1을 저장해주었다.

 

다음은, 6에 대한 NGE를 검사해야 한다.

 

먼저, Stack의 Top을 보자. Top의 값은 현재 10이다.

이 Top의 값이 현재 원소의 NGE가 된다.

즉, 6의 NGE는 10이 된다.

 

이렇게, NGE를 갱신해준 뒤 6또한 다시 Stack에 삽입해주었다. 

 

다음 3에 대해서도 똑같은 과정을 거치면 된다.

현재 stack 의 top은 6이다. 6은 3보다 큰 값이기 때문에, 6은 3의 NGE라고 할 수 있다.

그러므로 아래와 같이 Answer 배열을 갱신해주면 된다.

Answer배열을 갱신해주고, Stack에 3을 삽입하였다.

5에 대해서 동일한 과정을 거치려고 하니까, 한가지 문제가 발견되었다.

Stack의 Top이 5보다 작기 때문에, Stack의 Top을 NGE라고 할 수가 없어져버린 것이다.

이럴 땐, Stack의 Top이 5보다 커질때까지, Stack에서 pop을 하면 된다.

이렇게 스택에서 3을 pop했더니, top이 5보다 큰 값이 되었다.

이 값이 5의 NGE가 되는 것이다.

그러므로, 배열을 아래와 같이 갱신해주면 된다.

스택에 본인을 삽입해주는 것도 잊지 말자.

 

7에 대해서도 동일한 과정을 거치면 된다.

Stack에서 5를 pop하고, 6을 pop하면 top은 10이 된다.

그러므로, 10을 7의 NGE로 저장한 뒤, 7을 다시 Stack에 push해주면 된다.

 

마지막 1에 대해서도 동일한 과정을 거치면 최종적으로 아래와 같아진다.

처음에 보았던 기댓값과 Answer배열의 값이 완전히 동일한 것을 볼 수 있다.

 

PGE를 구하는 방법도 동일하다. 다만, 배열의 뒤에서부터 진행하는 것이 아니라 앞에서 부터 진행하면 된다.

이렇게 NGE를 구하는 과정에서 Stack의 원소를 보면, 항상 오름차순 형태를 유지하고 있다. 이러한 형태때문에 단조 스택(Monotonic Stack)이라는 이름이 붙은 것 같다.

 

코드 구현

std::vector<int> Array = {1, 7, 5, 3, 6, 10};
std::vector<int> Answer(Array.size(), 0);

std::stack<int> MonotonicStack;

 

먼저 이렇게 입력을 받고 사용할 스택도 선언해주었다.

 

다음은 배열을 순회하며 NGE를 구해줄 것이다.

for (int i = Array.size() - 1; i >= 0; i--)
{
    int CurNum = Array[i];

    while (MonotonicStack.size() > 0)
    {
        if (MonotonicStack.top() > CurNum)
        {
            break;
        }

        MonotonicStack.pop();
    }

    if (MonotonicStack.size() == 0)
    {
        Answer[i] = -1;
    }
    else
    {
        Answer[i] = MonotonicStack.top();
    }

    MonotonicStack.push(CurNum);
}

 

for문의 조건을 보면, 배열의 마지막원소부터 순회하는 것을 볼 수 있다.

스택의 top이 현재 값보다 큰 값이 될 때까지, 계속 pop을 해주고 있다. 만약 stack의 모든 원소를 pop했음에도 큰 값을 찾지 못했다면 NGE가 없는 것으로 간주하고 Answer을 -1로 갱신해주었다.

반대로, NGE를 찾았다면 그 값으로 Answer을 갱신하였다.

 

마지막으로, MonotonicStack에 자기 자신을 push해주면 된다.

 

반복문이 모두 끝나면, 아래와 같이 Answer 배열의 값은 갱신되어 있을 것이다.

위에서 보았던 기댓값과 완전히 일치하는 것을 알 수 있다.

 

만약 PGE를 구하고 싶다면, 동일한 코드에서 for문의 조건만 아래와 같이 수정하면 된다.

이렇게, 앞에서부터 탐색하게 되면 Answer의 값은 아래와 같이 갱신된다.

위에서 보았던 PGE의 기댓값과 동일하다.

 

코드 전문

#include <stack>
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> Array = { 1, 7, 5, 3, 6, 10 };
    std::vector<int> Answer(Array.size(), 0);

    std::stack<int> MonotonicStack;

    for (int i = Array.size() - 1; i >= 0; i--)
        
        int CurNum = Array[i];

        while (MonotonicStack.size() > 0)
        {
            if (MonotonicStack.top() > CurNum)
            {
                break;
            }

            MonotonicStack.pop();
        }

        if (MonotonicStack.size() == 0)
        {
            Answer[i] = -1;
        }
        else
        {
            Answer[i] = MonotonicStack.top();
        }

        MonotonicStack.push(CurNum);
    }

    return 0;
}