RE. [백준 6198] 옥상 정원 꾸미기 - C++ / 알고리즘 monotone stack

문제

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

6198번: 옥상 정원 꾸미기

나의 코드 - 하지만 틀림^^

#include <iostream>
#include <stack>

using namespace std;

int main() {
	stack<int> s;
	//빌딩 높이, 해당 높이 오른쪽에 낮은 빌딩 개수
	stack<pair<int, int> > building;
	int num, h, height;

	cin >> num;

	for (int i = 0; i < num; i++) {
		cin >> h;
		s.push(h);
	}

	int count, total = 0;
	while (!s.empty()) {
		height = s.top();
		s.pop();
		count = 0;

		while (!building.empty()) {
			if (height > building.top().first) {
				count += building.top().second;
				count++;
				building.pop();
			}
			else
				break;
		}
		building.push(make_pair(height, count));
		total += count;
	}
	cout << total;
}

 

검색해보니 'monotone stack' 알고리즘을 쓴다고 한다...!

https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/

monotone stack

 

monotone 알고리즘을 참고하여 다시 풀어봤지만 - 시간초과...ㅎ

 

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	
	stack<int> s;
	vector<int> vec;
	int num, input, total, count;
	
	cin >> num;

	total = 0;
	for (int i = 0; i < num; i++) {
		cin >> input;
		vec.push_back(input);
	}
	
	for (int i = 0; i < num - 1; i++) {
		s.push(vec[i]);
		count = 0;

		for (int j = i + 1; j < num; j++) {
			if (s.top() > vec[j]) {
				count++;
			}
			else
				break;
		}
		total += count;
		s.pop();
	}
	cout << total;
}

이렇게 풀면 monotone 의미가 없다... 그냥 벡터로 푼거랑 뭐가 다를까!!!(다른게 없지)

 

 

남의 코드 확인

결국 남의 코드를 보면서 이해하는 단계로 갔다 ㅠㅠ (반드시 다시 풀고 말테다)

스택에 대한 정확한 이해가 부족해서 그런 것 같다...

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	
	stack<int> s;
	vector<int> vec(80001);
	int num;
	long long ans = 0;

	cin >> num;

	for (int i = 0; i < num; i++) 
		cin >> vec[i];
	
	for (int i = 0; i < num; i++) {
		while(!s.empty() && s.top() <= vec[i])
			s.pop();  //vec[i]를 볼 수 없는 건물은 다 pop
		ans += (long long) s.size();
		s.push(vec[i]);
	}
	cout << ans << '\n';
}  

 

10은 3 자신을 볼 수 있는 건물이므로 pop하지 않고 ans에 1를 더한다.

하지만 7인 경우 3은 자신을 내려다 보는 건물이 아니므로 pop()한다.

 

그림으로 확인하니 왜 이 문제가 스택으로 그것도 'monotone stack 알고리즘'으로 풀어야하는지 이해가 되었다.

3인 경우: 10은 자신을 내려다보는 건물이므로 1을 추가한다.

7인 경우: 3은 7보다 작은 숫자이므로 pop하고 나머지 크기를 계산하여 더한다.

4인 경우: 10, 7은 모두 4보다 큰 숫자로 4 자신을 내려다보는 건물이므로 크기를 계산하고 더한다.

12인 경우: 12보다 작은 숫자를 모두 pop한다.

2인 경우: 자신을 내려다보는 건물은 12뿐이다.(12보다 작은 건물은 어차피 2를 볼 수 없다)

 

결국 자신보다 작은 숫자들은 버리고 순서대로 내림차순으로 정렬하는 스택의 기법을 확인할 수 있다.