단조 스택(Monotonic Stack) 이란
단조 스택(Monotonic Stack)은 스택(Stack) 자료 구조의 변형 중 한 개로 스택의 원소들이 단조 증가 혹은 단조 감소 상태인 스택을 말한다. 겉보기에는 힙(Heap) 자료구조와 비슷하게 보이지만 다르다. 정확하게 말하자면 단조 스택이란 스택에 원소를 삽입할 때 스택의 상태가 단조 증가 혹은 감소를 유지되는 것을 말한다.
사실 단조 스택은 자주 쓰이지는 않는다. 하지만 특정 문제에서는 단조 스택이 힘을 발휘할 때가 있다. 그중 한 개는 자신보다 처음으로 크거나 작은 원소의 값을 찾는 문제(Next Greater or Smaller Element)이다. 예를 들어 배열 [2, 1, 2, 4, 3]가 주어졌을 때 자신보다 처음으로 큰 원소를 저장하는 배열은 [4, 2, 4, -1, -1]이다. (만약 없다면 -1을 반환한다.) 완전 탐색 알고리즘을 사용할 경우 \(O(N^2)\)에 해결할 수 있지만 단조 스택을 사용하면 \(O(N)\)으로 해결 가능하다.
// 완전 탐색으로 찾기
// arr : input array
// ans : answer array
// n : input array length
memset(ans, -1, sizeof(ans));
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(arr[i] < arr[j]) {
ans[i] = arr[j];
break;
}
}
}단조 스택 만드는 과정
단조 스택을 만드는 과정은 단순하다. 만약 단조 증가하는 스택을 만든다면 원소를 삽입할 때 스택의 탑(top)이 삽입할 원소보다 작을 때까지 스택의 원소를 삭제한 후에 삽입하면 된다. 예를 들어 배열 [1, 3, 2, 4, 2]이 있을 때 단조 증가 상태를 유지하면서 스택에 원소를 하나씩 삽입해보자. 처음에는 스택이 비어있어 첫 번째 원소 1은 스택에 삽입된다.
두 번째 원소 3은 스택의 탑보다 커 스택에 삽입된다.
세 번째 원소 2는 스택의 탑보다 작아 스택의 탑이 2보다 작거나 스택의 원소가 없을 때까지 원소를 삭제한 후 삽입할 수 있다.
네 번째 원소 4는 스택의 탑보다 커 스택에 삽입된다.
다섯 번째 원소 2는 스택의 탑보다 작아 스택의 탑이 2보다 작거나 스택의 원소가 없을 때까지 원소를 삭제한 후 삽입할 수 있다.
의미하는 것
단조 증가 스택을 사용하면 어떤 원소 \(x\) 보다 왼쪽에 있는 원소 중에서 처음으로 \(x\) 미만의 원소를 알 수 있다. 배열 [1, 3, 2, 4, 2]에서 두 번째 원소 3을 삽입하는 과정에서 스택의 원소를 삭제한 후 스택의 탑 1은 배열에서 두 번째 원소 3보다 왼쪽에 있는 원소들 중에서 처음으로 3 미만의 원소이다.
세 번째 원소 2를 삽입하는 과정에서 스택의 원소를 삭제한 후 스택의 탑 1은 배열에서 세 번째 원소 2보다 왼쪽에 있는 원소들 중에서 처음으로 2 미만의 원소이다.
다섯 번째 원소 2를 삽입하는 과정에서 스택의 원소를 삭제한 후 스택의 탑 1은 배열에서 다섯 번째 원소 2보다 왼쪽에 있는 원소들 중에서 처음으로 2 미만의 원소이다.
정리
정리하자면 다음과 같다.
- 단조 증가 스택을 사용하면 현재 원소 \(x\) 보다 왼쪽에 있는 원소들 중에서 처음으로 \(x\) 보다 작은 원소를 알 수 있다.
- 단조 감소 스택을 사용하면 현재 원소 \(x\) 보다 왼쪽에 있는 원소들 중에서 처음으로 \(x\) 보다 큰 원소를 알 수 있다.
- 단조 증가 스택에서 원소 \(x\)를 삽입할 때 현재 스택의 사이즈는 현재 원소 \(x\) 보다 왼쪽에 있는 원소들 중에서 \(x\) 보다 작은 원소의 개수이다.
- 단조 감소 스택에서 원소 \(x\)를 삽입할 때 현재 스택의 사이즈는 현재 원소 \(x\) 보다 왼쪽에 있는 원소들 중에서 \(x\) 보다 큰 원소의 개수이다.
그렇다면 배열 [2, 1, 2, 4, 3]가 주어졌을 때 자신보다 처음으로 큰 원소를 저장하는 배열은 [4, 2, 4, -1, -1]을 찾는 방법은 간단하다. 배열을 뒤집어 단조 감소 스택을 만들어 쉽게 해결할 수 있다.