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

문제 링크: https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

[문제 풀이] 스택, 자료구조

 

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

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

먼저 크기가 N인 배열을 준비합니다.

arr[i]는 i번째 빌딩을 바라보는 관리자들의 수가 됩니다.

->arr[1] == 0 (어떤 빌딩도 바라볼 수 없음)

   arr[2] == 1 (1번 빌딩이 바라보고 있음)

   arr[3] == 1 (1번 빌딩이 바라보고 있음)

   arr[4] == 2 (1번, 3번 빌딩이 바라보고 있음)

   arr[5] == 0 (어떤 빌딩도 바라볼 수 없음)
   arr[6] == 1 (5번 빌딩이 바라보고 있음)

 

그리고 빌딩을 저장할 수 있는 스택을 하나 준비합니다

이때 스택엔 i번째 빌딩을 볼 수 있는 빌딩을 저장합니다. 

-> 1번 빌딩 stack = {0}

    2번 빌딩 stack = {0, 1}

    3번 빌딩 stack = {0, 1}    

    4번 빌딩 stack = {0, 1, 3}

    5번 빌딩 stack = {0}

    6번 빌딩 stack = {0, 5}

 

스택의 size -1은 i번째 빌딩을 바라볼 수 있는 관리자의 수가 됩니다.

 

1 ~ N 빌딩을 순회하면서

i 번째 i +1 번째 빌딩을 체크해서

 

if(i + 1 번째 i번쨰 빌딩보다 작으면)

->i번째 빌딩이 i+1번째 빌딩을 볼 수 있으니깐 i번쨰 빌딩을 스택에 추가합니다.

else if(i +1번째 빌딩이 i번쨰 빌딩보다 크거나 같으면)

->i+1번째 빌딩을 볼 수 없는 관리자들을 스택에서 제거합니다.

  ex) 5번 빌딩일 때 1번, 3번을 제거함)

 

 

 

<c++ 소스 코드> 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <numeric>
using namespace std;
 
int height[80001];
int sum[80001];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> height[i];
    }
    
    stack<int> manager; //스택의 관리자들은 i번째 빌딩을 볼 수 있다
    manager.push(0);
    for (int i = 1; i <= n; i++) {
        sum[i] = manager.size() - 1;//i번째 빌딩을 바라보는 관리자들의 수
        if (height[i + 1] < height[i]) {//다음 빌딩이 더 작으면 i번째 빌딩이 다음 빌딩을 볼 수 있음
            manager.push(i); //i번째 빌딩을 i+1번째 빌딩을 볼 수 있는 관리자로 추가
        }
        else if (height[i + 1] >= height[i] && manager.top()) { // 다음 빌딩이 더 크거나 같으면
            //다음 빌딩을 볼 수 없는 관리자들을 스택에서 제거
            while (height[manager.top()] <= height[i + 1] && manager.top()) manager.pop();
 
        }
    }
    long long res = 0;
    cout << accumulate(sum + 1, sum + n + 1, res);
    return 0;
}