[백준 - 6198] 옥상 정원 꾸미기 - C++

분류: 스택 /

 

문제

문제 링크

문제 설명

도시에는 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이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 h_i 입력된다. (1 ≤ h_i ≤ 1,000,000,000)

출력

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

 

풀이

#include <iostream>
#include <stack>
using namespace std;

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

  long long ans=0;
  int n;
  cin >> n;
  stack<int> S;
  while(n--){
    int h;
    cin >> h;
    while(!S.empty() && S.top() <= h)
      S.pop();
    
    // 어차피 empty일 때 size는 0이므로 if문을 지워도 된다.
    // 연산의 수를 줄이기 위해 if를 넣었다.
    if(!S.empty())
      ans += S.size();
    S.push(h);
  }
  cout << ans;
}

문제를 조금 바꿔 이해해보면 "각 빌딩에서 볼 수 있는 옥상의 수의 합"은 "각 빌딩의 옥상을 볼 수 있는 빌딩 수의 합"과 같다.

문제의 예시를 바뀐 문제로 이해해보면 다음과 같다.

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

• 1번 빌딩의 옥상을 볼 수 있는 빌딩은 없다.
• 2번 빌딩의 옥상을 볼 수 있는 빌딩은 1번 빌딩 1개 이다.
• 3번 빌딩의 옥상을 볼 수 있는 빌딩은 1번 빌딩 1개 이다.
• 4번 빌딩의 옥상을 볼 수 있는 빌딩은 1, 3번 빌딩 2개 이다.
• 5번 빌딩의 옥상을 볼 수 있는 빌딩은 없다.
• 6번 빌딩의 옥상을 볼 수 있는 빌딩은 12번 빌딩 1개 이다.

따라서, 각 빌딩의 옥상을 볼 수 있는 빌딩 수의 합은 0 + 1 + 1 + 2 + 0 + 1 = 5이다.

 

`monotonic decreasing stack`을 만들면 스택에 저장된 빌딩들(while문 이후)은 새로운 입력 `x`를 볼 수 있는 빌딩들 이다. 따라서 `x`의 옥상을 볼 수 있는 빌딩의 수는 스택의 사이즈와 같다.