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

6198번: 옥상 정원 꾸미기

스택을 이용한 문제이다. 로직 자체는 간단한데 이것을 이해하는데 생각보다 오래 걸렸다... 먼저 첫번째 건물 높이를 스택에 넣어준다. 그 뒤 반복문을 돌면서 스택의 top과 현재 인덱스의 건물 높이와 비교하게 되는데 만약 top이 볼 수 없는 높이라면 pop을 해주게 된다. 이렇게 되면 스택에 남은 값은 현재 인덱스의 건물 높이보다 크므로 건물을 볼 수 있는 건물들임을 의미한다. 스택의 크기를 result에 더해주고 이를 반복한 뒤 출력해주었다. 로직을 이해하는데 꽤 오래 걸린 문제였다. 이와같은 유형의 문제를 잘 새겨두어야겠다.

#include <iostream>
#include <stack>

using namespace std;

int N;
int A[80000];
long long result = 0;

void solution() {
    stack<int> s;

    s.push(A[0]);

    for (int i = 1; i < N; i++) {
        while (!s.empty() && s.top() <= A[i]) {
            s.pop();
        }
        
        result += s.size();

        s.push(A[i]);
    }

    cout << result;
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}