[Baekjoon] 6198번: 옥상 정원 꾸미기

🥅 문제

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

 

🔍 설계

처음에는 벡터에 높이들을 모두 저장하고, 이중 반복문을 수행하려고 했으나, 시간 복잡도 O(N^2)에 의해 시간 초과가 발생할 것이다.

 

건물 관리인들은 오른쪽만 보기 때문에, 반복문으로 건물 하나의 높이를 고려하면서, 스택에 그 건물을 볼 수 있는 다른 건물들을 저장한다. 

 

만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 낮거나 같다면, 새로운 건물과 이후에 나오는 건물들을 볼 수 없으므로 이제 결과에 영향을 주지 않기 때문에 지운다.

 

만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 높다면, 그 건물에서 새로운 건물을 볼 수 있으므로 스택에 있는 건물의 개수를 추가한다.

 

👊 풀이

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

int n, h;
long long result = 0;
stack<int> s;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h;
		while (!s.empty() && s.top() <= h) {
			s.pop();
		}
		if (s.empty()) {
			s.push(h);
		}
		else if (s.top() > h) {
			result += s.size();
			s.push(h);
		}
	}
	
	cout << result << "\n";
	return 0;
}

 

📝 메모

모두 내림차순으로 되어있는 경우, 79999 + 79998 + ... + 1 = 80000 * 40000으로 int 범위를 초과할 수 있다.