[BOJ/C++] 옥상 정원 꾸미기(6198번)

1. 개요

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

1-1. 설명

도시에는 N개의 빌딩이 있으며, 빌딩 관리인들은 다른 빌딩의 옥상 정원을 벤치마킹 하고싶어 한다. i번째 빌딩의 키가 h_i이고 모든 빌딩은 일렬로 서있으며 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, ... , N이다. 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 다음에 있는 모든 옥상은 보지 못한다.

각 관리인들의 벤치 마킹이 가능한 빌딩의 수의 합을 출력한다. 

1-2. 제한 사항

 - 첫 줄에 빌딩의 개수 N이 주어지며, N은 1 이상 80,000 이하 자연수

 - 두 번째 줄부터 N + 1번째 줄까지 각 빌딩의 높이가 h_i 주어지며, h_i는 1 이상 1,000,000,000 이하 자연수

 - 각 관리인들의 벤치 마킹이 가능한 빌딩 수의 합을 출력

 

---

2.구현

2-1. 풀이

Stack임을 알고 있었으나, 정확히 어떻게 풀어야할지 감이 안와 풀이를 참조하였다. 

단조 스택을 이용하는 방법이었으며, 내림차순 단조 스택을 이용하여 풀었다. 단조스택의 설명은 해당 링크를 참조한다. 

반복문을 통해 현재 빌딩 건물을 기준으로 스택이 비어있으면 push를 해주고, 비어있지 않고 스택의 top과 비교했을 때 현재 건물보다 이전 건물(top)이 낮으면 pop을 해준다. 그리고 각 반복문마다 스택의 size가 관찰 가능한 빌딩의 개수이므로 이를 모두 더하면 관찰 가능한 빌딩 수의 합이 된다. 

2-2. 코드

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

using namespace std;

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

    int N, height;
    long long result = 0;

    cin >> N;
    vector<int> heights;
    while (N--) {
        cin >> height;
        heights.push_back(height);
    }

    stack<int> st;

    // 각 건물마다 빌딩 관찰 가능 시점을 stack에 저장 후 저장되어 있던 순간의 합이
    // 각 빌딩에서 관찰 가능한 빌딩의 개수가 됨
    for (int element : heights)
    {
        if (st.empty()) st.push(element);
        else {
            if (st.top() > element) st.push(element);
            else if (st.top() <= element) {
                while (!st.empty() && st.top() <= element) st.pop();
                // 현재 건물보다 이전 건물이 낮으면 pop
                st.push(element);
            }
        }
        result += (st.size() - 1);
    }

    cout << result;
}