[백준 6198] 옥상 정원 꾸미기 (C++)

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    stack<int> holds;
    vector<long long int> buildings;
    long long int answer = 0;

    long long int input;
    for (int i = 0; i < n; i++) {
        cin >> input;
        buildings.push_back(input);
    }

    for (int i = 0; i < n; i++) {
        while (!holds.empty() && holds.top() <= buildings[i]) {
            holds.pop();
        }
        answer += holds.size();
        holds.push(buildings[i]);
    }

    cout << answer;

    return 0;
}

이번 문제 해결은 정말 쉽지 않았다. 아무리 그림을 그려 알고리즘을 디자인해도 어떻게 스택 자료구조를 활용할 수 있을지 도저히 답이 나오지않았고, 결국 풀이를 보고야 말았다.

여기서 활용된 기법은 모노톤 스택(Monotonic Stack, 단조성 스택)이다. 일정한 기준에 따른 단조성을 유지하는 스택구조를 활용하는 것으로 높이, 가격, 길이 등의 조건의 오름차/내림차순에 따라 스택 내부 데이터의 순서를 유지한다.

이 모노톤 스택 기법을 활용해 건물의 오름차순 정렬을 유지하고 스택의 top보다 큰 건물이 등장하면 스택 데이터를 pop한다. pop이 끝나면 남은 스택의 size를 더해줌으로써, 관리인들이 옥상정원을 확인할 수 있는 총 수를 구할 수 있었다.