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

문제

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

풀이

처음 풀이

vector의 빌딩들의 높이를 차례대로 할당한 후 빌딩별로 자신보다 높거나 같은 빌딩이 나올때까지의 빌딩 수를 count하는 방식으로 풀었다.

이 방법은 이중 for문을 사용해서 시간복잡도는 O(N^2)이다.

하지만 시간복잡도를 O(N)으로 줄이는 방법이 있다는데.....

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

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

   int n;
   long long ans = 0;
   cin >> n;
   vector<int> h(n, 0);
   for (int i = 0; i < n; i++)
      cin >> h[i];

   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (h[i] <= h[j]) break;
         ans++;

      }
   }
   cout << ans;
}

monotonic stack

monotone stack은 스택의 원소들이 오름차순 or 내림차순 상태를 유지하도록 하는 것이다.

만약 다음과 같은 수를 스택에 집어넣는다고 가정하자.

5 19 46 20 10 16 18 15 15 29 47 20

 

46까지는 기존 stack 처럼 들어가지만

20의 경우 46보다 작으므로 46을 pop하고 push 한다.

나머지도 똑같이 처리하면 다음과 같다.

monotonic stack 자체로는 의미가 별로 없지만 새로운 원소가 입력됐을 때, 정렬하는 과정에서 발생하는 정보들이 유용하다고 한다.

예시

• 정렬하는 과정에서 각 원소의 Next Greatest Number를 찾을 수 있다.
• https://iridescentboy.tistory.com/146

Monotonic Stack, 단조 스택이란?

향샹된 풀이

monotonic stack을 활용하면 O(N)에 이 문제를 풀 수 있다고 한다..

일단 풀이를 먼저 보자면 다음과 같다.

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

int main(){
    int n;
    stack<int> s;
    long long ans;
    cin >> n;
    
    long long h;
    while(n--){
        cin >> h;
        while(!s.empty() && s.top() <= h)
            s.pop();
        ans += s.size();
        s.push(h);
    }
    cout << ans;
}

처음엔 이게 어떻게 풀리는 건지 이해를 제대로 못했는데 monotonic stack에 빌딩을 추가할때마다 이전 빌딩이 stack에 남아있게 된다면 자신이 볼 수 있는 옥상이 하나 늘어난 것으로 보고 살아남은 빌딩만큼 count 를 추가해준다고 이해했다.

monotonic stack은 내림차순으로 정렬한다고 하고

만약 {10, 7} 이 스택에 있고 높이가 4인 빌딩을 정렬할려고 할 때

높이 10, 7인 빌딩은 높이 4 빌딩을 참고할 수 있으므로 총 2개의 참고개수가 증가한다.(스택의 size인)

monotonic : {10, 7}
if push 4:
	count += 2
    monotonic : {10, 7, 4}

 

다음에 높이 12인 빌딩이 들어온다면

{10, 7, 4} 빌딩들은 참고할 수 없으므로 stack에서 pop되고 참고개수는 stack의 size가 0이므로 증가하지 않는다.

monotonic : {10, 7, 4}
if push =12:
	pop {10, 7, 4}
	count += 0
    monotonic : {12}

 

즉 monotonic stack의 원소들은 현재 추가되는 빌딩을 참고할 수 있는 빌딩들이라고 생각하면 된다.