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

문제

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.
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번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

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

풀이

풀이 1 - 탑 2493 참고

조건
1. 자기보다 뒤에 있는 건물
2. 자기보다 키가 낮은 건물
두가지 조건을 만족하는 건물의 개수의 합

building.push({1000000001, 0}); //탑 높이제한 1,000,000,000
    
    for(int i=1; i<=n; i++){
        int height;
        cin >> height; 
        
        //현재 스택에 들어있는 top이 입력받은 빌딩의 높이보다 낮으면
        while(building.top().first < height)
            building.pop(); 
            
        cout << building.top().second<<" "; //0
        building.push({height, i});
    }

입력 예제 : 10 3 7 4 12 2 일 때 코드 수행 과정
1. 10일때 스택에 아무것도 없으므로 그냥 push

2. 3 일때 top=10 > 3이므로 push
   

3. 7 일때 top=3 < 7 이므로 pop()
   
   - top=10 < height=7이므로 while문 빠져나와서
   

-> 해당 코드가 뭘 의미하는가??

작성중인 코드

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

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    //1. n개 입력받기
    int n;
    cin >> n;
    
    //2. 빌딩 높이 , 관리인 번호를 저장하는 pair 만들기
    //pair<빌딩 높이, 관리인 번호>
    stack<pair<int, int>> building; 
    int ans=0;
    
    for(int i=1; i<=n; i++){
        int height;
        cin >> height; 
        
        //현재 스택에 들어있는 top이 입력받은 빌딩의 높이보다 높으면
        //10 3 7 4 12 2
        while(building.top().first < height && !building.empty())
            building.pop(); 
        ans += 
            
        cout << building.top().second<<" "; //0
        building.push({height, i});
    }
    
    return 0;
}

하나의 탑을 수신받을 수 있는 탑이 오직 하나였던 탑의 문제와는 살짝 다르다.

풀이 2

1. 자기보다 뒤에 있는 건물

2. 자기보다 키가 낮은 건물
   둘을 만족하는 건물 개수의 합을 구하시오.

3. 나보다 키가 큰 애(옥상 정원을 볼 수 없는 애)는 pop

4. 나보다 키가 작은 애의 개수 ++

5. 내 키와 idx를 stack에 저장

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


int N;
stack<int> tower;

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

  cin >> N; 
  int sum=0;
  
  for (int i = 1; i <= N; i++) {
    int height;
    cin >> height;
    
    while (tower.top() <= height && !tower.empty()) {
        tower.pop(); 
        sum++; //이 부분 틀림
    }
    
    tower.push(height);   
  }
}

풀이 3 - 정답 코드

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


int N;
stack<int> tower;

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

  cin >> N; 
  long long sum=0;
  
  for (int i = 1; i <= N; i++) {
    int height;
    cin >> height;
    
    while (!tower.empty() && tower.top() <= height) { // && 앞뒤 순서 바뀌면 안됨
        tower.pop(); 
    }
    
    sum += tower.size();
    
    tower.push(height);   
  }
  
  cout << sum;
}

참고

https://programforlife.tistory.com/53