단조 스택(Monotonic Stack)

1. 단조 스택이란?

스택 종류의 하나로 원소들이 증가하거나 감소하는 형태를 가짐.

스택을 이렇게 유지하면 이전/다음에서 더 작은/큰 값을 찾는데 사용할 수 있다.

2. 활용

배열의 각 원소에 대해, 왼쪽에 있는 원소들 중 자신보다 작은 값들 가운데 가장 가까이 있는 값을 구한다고 해보자.

1. 이중 for문을 통한 탐색

$O(\frac{N(N-1)}{2}) = O(N^2)$이다.

2. 단조 스택을 통한 탐색

단조 증가 스택을 사용해보자 (스택이 오름차순으로 정렬)
결론만 먼저 말하면 $O(N)$로 탐색할 수 있다.
일단 방법을 살펴보고 분석해보자.

• 2
  • top -> []
  • push 시점에 stack이 비어있으므로 2보다 작은 수는 없음.
  • res [-1,0,0,0,0]
  • top -> [2]
• 1
  • top -> [2]
  • top(2)이 1보다 크기 때문에 pop()
  • push 시점에 stack이 비어있으므로 1보다 작은 수는 없음.
  • res [-1,-1,0,0,0]
  • top -> [1]
• 4
  • top -> [1]
  • push 시점에 top(1)이 4보다 작으면서 가장 가까운 값
  • res [-1,-1,1,0,0]
  • top -> [4,1]
• 5
  • top -> [4,1]
  • push 시점에 top(4)이 5보다 작으면서 가장 가까운 값
  • res [-1,-1,1,4,0]
  • top -> [5,4,1]
• 3
  • top -> [5,4,1]
  • top(5)가 3보다 크기 때문에 top이 3보다 작거나 같을 때까지 pop
  • push 시점에 top(1)이 3보다 작으면서 가장 가까운 값
  • res [-1, -1, 1, 4, 1]
  • top -> [3,1]

값 대신 index를 넣어서 해당 값이 어디에 있었는지도 알 수 있다.

모든 원소를 순회하고, 여러번 pop하는 부분 때문에 $O(N^2)$으로 오해하기 쉽다. 하지만 다음을 잘 생각해보자

스택에서 각 원소는 한번씩만 push/pop 할 수 있다.
다시말해 전체 push/pop 횟수의 상한이 있다.
위의 예제에서도 같은 원소가 2번 이상 push되지 않았고, pop된 원소는 그대로 끝이다.
최악의 경우를 생각해도 N개의 원소가 N번 push되었다가 N번 pop될 뿐이다. 원소가 전부 스택에 들어갔다가 나와도 연산 횟수가 2N을 넘지 않는다.

수식으로 살펴보면

스택을 통한 탐색은 각 $1 + k_i$번의 연산을 한다.
$k_i =$ 해당 단계의 pop횟수
$\sum_{i=1}^{N}{k_i} \leq N$ 인 느낌이다.

전체적으로 보면
$\sum_{i=1}^{N}{(1 + k_i)} \leq 2N$ 이 된다.

3. 응용 문제

주식가격

단조 스택을 사용해서 쉽게 풀 수 있다. 단조 스택을 만들면 자연스레 가격이 떨어지지 않은 원소들만 남게 된다. pop을 하게 되는 경우 현재 시간에서 삽입된 시간을 빼서 정답 배열에 추가하면 된다.

보기 편한 풀이

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices) 
{
    vector<int> answer(prices.size(), 0);
    stack<pair<int, int>> priceStack;
    int time = 0;
    // 각 원소는 한번씩 push 와 pop을 한다.
    // 즉 N개 원소는 각각 N번의 push N번의 pop을 한다.
    // 2N -> O(N)
    for (auto it = prices.begin(); it != prices.end(); ++it)
    {
        time++;

        // top이 현재 가격보다 작거나 같을때 까지 pop
        while (!priceStack.empty() && priceStack.top().first > *it)
        {
            int insertTime = priceStack.top().second;
            priceStack.pop();
    
            //삽입된 시점에 가격을 유지한 시간 기록
            answer[insertTime - 1] = time - insertTime;
        }
  		// 스택에 값과 삽입된 시간 기록
        priceStack.push(make_pair(*it, time));
    }

    while(!priceStack.empty())
    {
        int insertTime = priceStack.top().second;
        priceStack.pop();
        answer[insertTime - 1] = time - insertTime;
    }

    return answer;
}

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices) 
{
    vector<int> answer(prices.size(), 0);
    stack<int> priceStack;
    // 각 원소는 한번씩 push 와 pop을 한다.
    // 즉 N개 원소는 각각 N번의 push N번의 pop을 한다.
    // 2N -> O(N)
    for (int i=0; i<prices.size(); i++)
    {
        // 
        while(!priceStack.empty() && prices[priceStack.top()] > prices[i])
        {
            answer[priceStack.top()] = i - priceStack.top();
            priceStack.pop();
        }

        priceStack.push(i);
    }

    while(!priceStack.empty())
    {
        answer[priceStack.top()] = prices.size() - 1 - priceStack.top();
        priceStack.pop();
    }

    return answer;
}