[백준] 6198. 옥상 정원 꾸미기 (Bad Hair Day)

[문제]

: 각 빌딩의 관리인들이 확인할 수 있는 옥상정원 수의 총합 구하기

 

입력 예시	출력 예시
6 //빌딩의 개수 N (1 ≤ N ≤ 80,000) 10 //각 빌딩의 높이 (1 ≤ hi ≤ 1,000,000,000) 3 7 4 12 2	5 (= 3+0+1+0+1+0)

 

 

[풀이]

문제에 제시된 예시를 보면, 1번 관리인은 2, 3, 4번 옥상을 확인할 수 있고, 2번은 다른 빌딩의 옥상을 확인할 수 없으며, 3번은 4번 옥상을 확인할 수 있다. 이를 반대로 생각해보면, 1번은 아무도 볼 수 없고, 2번은 1번에서만 볼 수 있다. 또한 3번은 1번에서만 볼 수 있고, 4번은 1, 3번에서만 볼 수 있다.

마찬가지로 5번은 아무도 볼 수 없고, 6번은 5번만 볼 수 있다.

 

이 발상을 이용하여 스택을 구현하면 문제는 해결된다.

 

스택의 크기(size)는 n번 빌딩을 볼 수 있는 빌딩 관리자의 수(n번 빌딩 관리자 포함)를 나타낸다. 즉, n번 빌딩에 대하여 우리가 구해야 할 관리자의 수는 (스택의 크기(size) - 1)이 된다.

 

문제에 나온 예시를 통해 자세히 알아보자.

 

1) 1번 빌딩: 맨 처음 빌딩이기 때문에 스택이 비어있으므로, 1번 빌딩의 높이(10)를 스택에 push한다. 이때 스택의 size가 1이므로, 1번을 볼 수 있는 관리자의 수는 1 - 1 = 0이다.

2) 2번 빌딩: 2번 빌딩의 높이(3)은 1번 빌딩의 높이(10)보다 작으므로 스택에 push한다. 이때 스택의 size는 2이므로, 2번을 볼 수 있는 관리자의 수는 2 - 1 = 1이다.

3) 3번 빌딩: 스택에는 1번과 2번의 높이(10, 3)가 들어있다. 3번 빌딩의 높이(7)은 스택의 top인 2번 빌딩의 높이(3)보다 크므로 3을 스택에서 pop하고 7을 push한다. 이때 스택의 size가 2이므로, 3번을 볼 수 있는 관리자의 수는 2 - 1 = 1이다.

4) 4번 빌딩: 스택에는 (10, 7)이 들어있다. 4번 빌딩의 높이(4)는 스택의 top인 7보다 작으므로 그대로 스택에 push한다. 이때 스택의 size는 3이므로, 4번을 볼 수 있는 관리자의 수는 3 - 1 = 2이다.

5) 5번 빌딩: 스택에는 (10, 7, 4)가 들어있다. 5번 빌딩의 높이(12)는 스택의 top인 4보다 크므로, 스택의 top이 12보다 커질 때까지(top > 12) pop을 한 후 12를 push한다. 결국 스택에서 10, 7, 4가 모두 pop이 되어 스택에는 12만 남게 된다. 따라서 최종적인 스택의 size는 1이므로, 5번을 볼 수 있는 관리자의 수는 1 - 1 = 0이 된다.

6) 6번 빌딩: 스택에는 12만 들어있다. 6번 빌딩의 높이(2)는 스택의 top(12)보다 작으므로 그대로 스택에 push한다. 이때 스택의 size는 2이므로, 6번을 볼 수 있는 관리자의 수는 2 - 1 = 1이다.

 

 

위의 방식대로 스택을 구현하면 아래와 같다.

 

#include <iostream>
using namespace std;
#include <stack>
#include <vector>
 
int n;
stack<long long> s;
 
int main()
{
    int i;
    long long sum = 0;
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    vector<long long> h(n);
    for (i = 0; i < n; i++) {
        cin >> h[i];
        while (!s.empty() && s.top() <= h[i]) s.pop();
        s.push(h[i]);
        sum = sum + s.size() - 1;
    }
    cout << sum << endl;
    return 0;
}