[알고리즘] Monotonic Stack

개요

자신보다 큰 값(혹은 작은 값)이 언제 처음 오는지에 대해 구해야 할 때, 가장 쉽게 떠올릴 수 있는 방법은 2중 for 문을 쓰는 것이다.

 

예를 들어 다음과 같이 숫자가 있다고 할 때

3 4 1 5 2

 

각각의 숫자에 대해 그 수보다 큰 수가 처음 등장하는 인덱스(0부터 시작)를 나타내면 다음과 같다.

num : 3(1) 4(3) 1(3) 5(x) 2(x)

 

2중 포문을 사용하게 되면, n개의 원소에 대해 시간 복잡도는 O(n^2)이다.

이를 스택을 사용하면 한 번만 순회를 돌면서, 즉 O(n)만에 자신보다 큰 인덱스를 찾을 수 있다.

 

Monotonic Stack

monotonic stack의 원리는 간단하다.

stack에 들어있는 원소가 내림차순(혹은 오름차순)이 되게 정리만 해주면 된다.

1. 즉, 원소를 삽입할 때 stack의 top이 원소보다 크면 stack을 pop해주는 과정을 반복하고

2. stack의 top보다 작거나 stack이 비어있게 되면 stack에 push 해주면 된다.

 

앞서 34152에 대한 예시는 다음과 같다. (num, idx)로 표시한다.

 

1. 3을 넣는다.

2. 4보다는 3이 작으므로 3을 pop 한다. 그리고 이때의 idx 1이 3보다 큰 수가 처음 등장하는 인덱스 이므로 3의 해당 값은 1이 된다. 그 후에 4를 넣는다.

3. 1은 4보다 작으므로 pop하지 않고 그냥 push 한다. stack의 상태는 4, 1이다.

4. 5는 1과 4 둘 보다 크다. 1과 4를 pop 하고 5를 push 한다. 4와 1의 idx값은 모두 3이 된다.

5. 2는 5보다 작으므로 그냥 push한다.

 

이 과정이 끝나도 꺼내지 못한 원소들은, 그 원소보다 큰 원소가 등장하지 않는 경우이다.

 

대표문제

백준 14719 빗물 : https://www.acmicpc.net/problem/14719

14719번: 빗물

위 문제는 n이 500밖에 안되어서 O(n^2)으로도 풀 수 있지만, n 값이 10만 이상처럼 커진다면 Monotonic Stack을 활용해야 한다.

 

백준 3015 오아시스 재결합 : https://www.acmicpc.net/problem/3015

3015번: 오아시스 재결합

n이 500,000이기 때문에 O(n^2)으로는 풀 수 없다.

 

백준 1725 히스토그램 : https://www.acmicpc.net/problem/1725

1725번: 히스토그램

내림차순 Monotonic Stack을 사용한 앞선 예시들과는 다르게 오름차순 Monotonic Stack을 사용해야 한다.