[백준 6198] 옥상 정원 꾸미기 - C++로 구현한 스택

문제 개요

• 문제 번호: 6198
• 제목: 옥상 정원 꾸미기
• 난이도: 골드 5
• 링크: 백준 6298번

---

문제 설명

도시에는 N개의 빌딩이 있다.

i번째 빌딩의 키가 h-i이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

---

접근 방법

이 문제는 빌딩을 순회하면서 빌딩이 오른쪽으로 몇채의 빌딩을 내려다 볼 수 있는지 묻는 문제다.

여기서 생각을 살짝 전환해야하는데 문제대로 빌딩이 오른쪽 방향으로 몇개의 빌딩을 볼 수 있는지가 아니라 현재 빌딩을 기준으로 왼쪽 방향에 몇채의 빌딩이 있는지 생각하면 편하다.

이렇게 스택에는 현재 빌딩보다 큰 빌딩들만 push하면 된다.

---

구현 코드

#include<iostream>
#include<stack>
#define endl "\n"

typedef long long ll;

using namespace std;

int N;
ll ans;
stack<int> s;

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

    cin >> N;

    while (N--)
    {
        ll h;
        cin >> h;

        while(!s.empty() && s.top() <= h)
            s.pop();
        ans += s.size();
        s.push(h);
    }
    
    cout << ans << endl;
}

---

코드 설명

1. 빌딩을 순회한다.
2. 현재 빌딩보다 작은 빌딩들은 모두 pop한다.
3. 스택에 남아있는 현재 빌딩보다 큰 빌딩들을 ans에 더한다.
4. 마지막으로 현재 빌딩을 스택에 push한다.

---

시간 복잡도

• O(N): N은 빌딩의 갯수

---

어려웠던 점

처음에 문제대로 현재 빌딩보다 작은 빌딩을 찾는 방식으로 생각헀더니 도저히 답이 안나왔다.

---

배운 점

문제를 그대로 해석하는게 아니라 반대로 생각하는 방법을 길러야겠다.