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

문제 설명

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

6198번: 옥상 정원 꾸미기

n개의 빌딩이 있고, 오른쪽의 빌딩만 볼 수 있다

자신이 위치한 빌딩보다 높거나 같은 빌딩이 있을 때, 그 다음에 있는 모든 빌딩의 옥상을 보지 못할 때, 관리인들이 옥상 정원을 확인 할 수 있는 수 구하기

 

문제 풀이법

문제에서 주어지는 문제 풀이 방법를 통해 문제를 풀려면, 풀리지 않는다

Monotone stack을 사용해야 한다

 

Monotone stack이란?

• 스택의 원소들을 O(n)의 시간복잡도로 오름차순 혹은 내림차순 상태로 유지하는 방법이다
• 스택의 top에 있는 숫자와 원하는 숫자와 비교한 후, 조건에 부합하면 pop을 하며 진행
  • 중복 없는 오름차순 스택 : s.top () >= tmp 인 경우에 pop()
  • 중복 없는 내림차순 스택 : s.top() <= tmp 인 경우에 pop()

 

풀이 과정

• 10을 입력 받았을 때
  • 스택은 비어있으므로 cnt에 스택의 사이즈인 0을 더한 후, 스택에 10을 push 한다
  • cnt = 0, stack => 10
• 3을 입력 받았을 때
  • 스택은 비어있지 않으므로, while문을 돈다 
  • s.top()인 10이 3보다 크므로 바로 while문을 빠져나간다
  • cnt에 스택의 사이즈인 1을 더한 후, 스택에 3을 push 한다
  • cnt = 1, stack => 10, 3
• 7을 입력 받았을 때
  • 스택은 비어있지 않으므로, while문을 돈다
  • s.top()인 3이 7보다 작으므로 pop()을 한다
  • s.top()인 10이 7보다 크므로 while문을 빠져나간다
  • cnt에 스택의 사이즈인 1을 더한 후, 스택에 7을 push 한다
  • cnt = 2, stack => 10, 7
• 4을 입력 받았을 때
  • 스택은 비어있지 않으므로, while문을 돈다
  • s.top()인 7이 4보다 크므로 while문을 빠져나간다
  • cnt에 스택의 사이즈인 2를 더한 후, 스택에 4를 push 한다
  • cnt = 4, stack => 10, 7, 4
• 12를 입력 받았을 때
  • 스택은 비어있지 않으므로, while문을 돈다
  • s.top()인 4가 12보다 작으므로 pop()을 한다
  • s.top()인 7이 12보다 작으므로 pop()을 한다
  • s.top()인 10이 12보다 작으므로 pop()을 한다
  • 스택이 비어있으므로 while문을 빠져나간다
  • cnt에 스택의 사이즈인 0을 더한 후, 스택에 12를 push 한다
  • cnt = 4, stack => 12
• 2를 입력 받았을 때
  • 스택은 비어있지 않으므로, while문을 돈다
  • s.top()인 12가 2보다 크므로 while문을 빠져나간다
  • cnt에 스택의 사이즈인 1을 더한 후, 스택에 1을 push 한다
  • cnt = 5, stack => 12, 1

=> 내가 내려다 보는 건물의 수가 아니라, 나를 내려다 보는 건물의 수를 구하는 것!

 

소스 코드

#include <iostream>
#include <stack>

using namespace std;

int main()
{   
    int n;
    cin >> n;
    
    stack<int> s;
    long long cnt = 0;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        
        while(!s.empty())
        {
            if (s.top() > tmp)
                break;
            s.pop();
        }
        
        cnt += s.size();
        s.push(tmp);
    }
    printf("%lld\n", cnt);

    return 0;
}