[알고리즘 연습] 옥상 정원 꾸미기 (백준 6198, C++)

옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

---

접근 방식 및 풀이

• 처음엔 '각 빌딩이 볼 수 있는 빌딩의 수'에 집중해 문제를 해결하고자 했다.
• 하지만 그렇게하니 2중 for문의 비효율적인 코드만 계속 도출되었고, 이것이 정답일리 없다고 생각했다.
• 꽤 오랜시간 고민한 끝에 '각 빌딩을 볼 수 있는 빌딩의 수'에 집중하는 방식을 떠올렸다.
• 그를 구현하기 위해 stack에 각 빌딩의 크기를 넣어가며 자신보다 작은 빌딩(자신을 볼 수 없는 빌딩)은 pop하고 stack의 size를 '각 빌딩을 볼 수 있는 빌딩의 수'로 삼고 결과에 더해줬다.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, number; 
    cin >> n;
    stack<int> s;

    long long ans = 0;
    for(int i=0; i<n; i++){
        cin >> number;
        while(!s.empty() && s.top() <= number) s.pop();
        ans += (long long)s.size();
        s.push(number);
    }
    cout << ans;
}

• 해당 코드로 제출한 결과 통과되었다.
• 이 때 정답이 최대 80000!이기 때문에 (빌딩의 수는 최대 80000개) 일반 int 자료형으로는 해결할 수 없다. 따라서 long long 자료형을 사용해주었다.