[자료구조] 백준 17298번: 오큰수 (C++), Monotonic Stack (단조로운 스택)

(이번 문제는 첫 골드 문제이다 (울컥))

이번 문제의 유형이 'Monotonic Stack'이라고 하는데 이 유형의 문제를 처음 접한 것은 아니다.

예전 SCPC 준비를 할 때, 같이 준비하던 친구들과 영어 문제를 풀면서 접했었던 경험이 있다.

많은 시간을 썼었지만 풀리지 않았었고, 해답을 찾다가 Monotonic Stack에 대한 자료가 많이 없어서 나중에 또 이런 유형을 만나게 되면 정리를 해둬야겠다고 생각했었다.

 

(해당 영어문제 링크)

https://www.acmicpc.net/problem/6105

6105번: Look Up

 

다시 이 유형의 문제를 만났을 때, 참고할만한 자료들을 찾다가 Monotonic Stack이 Monotone Stack, 단조 스택, 단조로운 스택 등 여러 이름으로 불리고 있었음을 알게 되었다.

 

자료를 보기 전까지는 '스택이 핵심이 되어야겠구나'를 생각하다가 '메인으로 사용되지 않고, 보조 느낌'으로 사용되는 듯했다.

---

도입

문제에서 요구하는 답은 이렇다.

예를 들어 {3, 5, 2, 7}과 같은 배열이 있고, 어떠한 배열의 원소(N)가 있을 때, N보다 큰 수가 N의 자리로부터 제일 처음 나타는 원소를 N으로 가져라(라는 느낌)

 

 완전 탐색으로 해당하는 원소들을 찾기에는 Ai의 범위가 1,000,000까지 가진다.

즉, O(1,000,000 x 1,000,000)이면 시간 복잡도가 과하게 넘쳐난다.

이래서 Monotonic Stack이 필요하다던데 (잘하는 사람들은 무의식적으로 사용한다고... 천잰가)

---

개념 (도출해야 하는 것)

그림으로 설명! (예제 1번 가져옴)

이러한 배열이 있다고 가정해보자.

이 배열은 이렇게도(높이에 따라) 나타낼 수 있다.

이렇게 보았을 때 문제에서 요구하는 건 아래 그림처럼 이해할 수 있다.

0번째 인덱스의 원소 3은 1번째 원소 5가 3보다 더 커서 5를 가지게 된다.
다른 인덱스들도 마찬가지
허나, 3번째 인덱스의 원소 7은 보다 큰 게 없으므로 문제에서 -1을 가지게 했으므로 -1을 가진다.

결과적으로 각 인덱스가 {5, 7, 7, -1}을 갖는 배열이 되어야 한다.

 

그렇다면 여기서 어떻게 스택이 사용되는가

 

---

개념 (스택 사용)

(예제 1의 경우를 그대로 사용한다.)

우선, 다음 내용을 숙지하고서 원리에 대해 알아보자.

문제를 풀기 위해 지금부터 스택을 사용할 것이다.
1. 스택이 텅 빈 경우 해당 인덱스에는 -1을 넣는다. (나중에 설명하겠지만 -1을 넣는 경우는 해당 인덱스의 원소보다 큰 게 없다는 뜻이다.)
2. 스택에 원소를 하나하나 넣을 것이다. (한 번에 다 넣어서 하나씩 pop 하는 그런 유형의 알고리즘이 아니다.)
3. 마지막 원소부터 시작한다. (이건 코드를 보면서 설명!)

[코드 설명]
1. arr에 입력을 받았다.
2. 결과물은 answer 배열에 담을 것이다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> arr;
	for (int i = 0; i < n; i++) { // 입력
		int a;
		cin >> a;
		arr.push_back(a);
	}

	vector<int> answer(n, 0);
	stack<int> s;

	for (int i = arr.size() - 1; i >= 0; i--) { // 역순으로
		while (!s.empty() && arr[i] >= s.top()) { // 이 과정에 대한 이해가 중요
			s.pop();
		}

		if (s.empty()) {// 비어있다는 것은 해당 인덱스의 원소가 다음 원소들 보다 크다는 뜻
			answer[i] = -1;
		}
		else {
			answer[i] = s.top();
		}

		s.push(arr[i]); // 스택에는 원소들을 무조건 넣어서 다음 for문의 while에서 비교해야한다.
						// 조건에 따라 스택에 넣는 경우는 없다.
	}

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << ' ';
	}

	return 0;
}

 

우선, 마지막부터 시작하기 때문에 7을 담는다는 과정이 이렇다.

첫 번째 while문은 조건에 맞지 않아 통과한다.

그리고, 스택은 비어있기 때문에 answer의 마지막 원소는 -1이 된다.

조건문들을 끝내고, 스택에다가 7을 담아준다.

 

다음 2를 담을 때는 다음 조건을 이해해보자.

while (!s.empty() && arr[i] >= s.top()) { // 이 과정에 대한 이해가 중요
	s.pop();
}

우선 스택은 비어있지 않다. (7이 담겨 있음)

그리고, 2는 현재 스택의 top 7보다 크지 않기 때문에 조건문을 통과하지 않는다.

else {
	answer[i] = s.top();
}

스택은 현재 비어있지 않아서 if문이 아닌 else문으로 간다.

answer 2번째 인덱스에 현재 스택의 top인 7이 들어간다.

 

그리고, 2를 스택에다가 넣어준다.

다음 for문의 while문에서 1번째 인덱스(5)의 차례가 되는데

5는 2보다 크기 때문에 pop이 되고, 7보다는 작기 때문에 while문을 끝내고

조건문으로 넘어간다.

 

과정을 이해하기 위해 2가 아니라 8이었을 때 과정을 그려보자.

while (!s.empty() && arr[i] >= s.top()) { // 이 과정에 대한 이해가 중요
	s.pop();
}

8이었다면 조건문을 만족할 때까지 stack을 pop 해나간다.

그리고 stack은 비어있기 때문에 if문을 통과할 것이다.

if (s.empty()) {// 비어있다는 것은 해당 인덱스의 원소가 다음 원소들 보다 크다는 뜻
	answer[i] = -1;
}

그리고, 8을 stack에다가 넣어준다.

 

2일 때와 8일 때를 도식화하면 이와 같다.

[2일 때]

[8일 때]

즉, 조건문을 통과하여 남은 스택의 top들을 활용하여 담아내는 구조이다.

---

결론

결론적으로 monotonic stack에서는 stack과 stack의 top 특성을 살려 문제를 풀어나가는 알고리즘(?)이다.

stack에 관한 것이라 자료구조에 넣어두었지만 알고리즘이라고도 볼 수 있을 거 같다.

 

코드와 도식화된 자료들을 연관 지어가면서 보면 보다 빠르게 이해할 수 있을 거 같다.

 

왜 단조로운 스택인지는 이해하지 못했지만 아마 결과적으로 나온 배열이 단조로운 구조(?)를 가져서 그런가 싶다.