[백준 6549] 히스토그램에서 가장 큰 직사각형

문제

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

 

알고리즘

스택

 

풀이

문제 이름에 이미 문제 내용이 적혀 있습니다. 이와 동일한 문제를 이미 분할정복으로 풀이 한 바 있습니다. 여러 가지 풀이가 가능하므로 이번에는 스택으로 풀어보도록 합시다.

 

문제에서 주어지는 직사각형 $N$개에 대해 다음과 같은 사각형을 정의하겠습니다. $i$번째 직사각형을 최대 높이로 하고 가장 넓은 사각형을 최대 사각형이라고 합시다. 이 최대 사각형이란 녀석은 다음과 같은 특징을 갖고 있습니다. 이 사각형의 가장 왼쪽과 오른쪽은 $i$번째 직사각형보다 낮은 사각형들로 막혀있습니다.

 

즉 $i$번째 최대사각형을 막는 제일 왼쪽과 오른쪽을 left [i]와 right [i]라고 할 때, 이들을 구하기 위해선 사각형 개수에 비례하는 $O(N^2)$의 시간 복잡도를 요구합니다. 이를 개선하기 위해 이전에 사용한 정보를 재활용합시다.

 

0번 직사각형부터 $N-1$번 직사각형까지 차례로 탐색해 나가며 각각의 left와 right가 결정되는 순간 해당 인덱스의 최대사각형을 구할 수 있습니다. 각 직사각형의 높이는 $h [i]$라고 하겠습니다.

 

 처음 0번 직사각형은 left와 right가 결정되지 않았습니다. 0번의 왼쪽에는 아무것도 없으므로 left는 -1이라고 할 수 있지만, 우리는 뒤에 나올 사각형에 대한 정보를 아직 모르기 때문에 right는 결정 불가능합니다.

 다음으로 1번 사각형을 보겠습니다. 경우의 수는 크게 3가지로 나뉩니다. 

 

1)  $h[0]$<$h[1]$

0번 사각형 입장에서는 자신의 최대 사각형을 더 확장해 나갈 수 있어 right를 현재 결정하지 않지만 1번 사각형 입장에서는 0번 사각형이 자신의 최대사각형을 가로막고 있습니다. 그러므로 1번 사각형의 left 또한 결정이 되지만 두 직사각형의 right는 아직 결정이 되지 않았습니다.

 

2) $h [0]$>$h [1]$

0번 사각형의 최대 사각형이 1번 사각형에 가로막혀 right가 결정됨에 따라 0번사각의 최대사각형이 결정되었습니다.

추후 다른 사각형들의 최대 사각형을 구할 때도 0번 사각형은 아무런 영향을 끼치지 않습니다. 1번 사각형의 최대 사각형은 아직 모릅니다.

 

3) $h [0]$=$h [1]$

이 경우는 두 직사각형의 최대 사각형이 일치합니다. 즉 0번의 최대 사각형을 고려하지 않아도 자연스레 1번의 최대사각형을 구하는 과정에서 해결 가능하므로 2) 케이스와 마찬가지로 처리합니다.

 

위 케이스대로 진행해 나가며 결정이 되지 않은 직사각형은 스택에 넣어 계속해서 자신의 right를 찾아나갑니다.

이러한 스위핑으로 선형시간 $O(N)$에 해결 가능합니다.

 

++

알고리즘 문제해결 전략 제 2권을 참고하여 작성했습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;

ll N,h[100001];

int main() {
    FAST;
    
    while (1) {
        cin >> N;
        if (!N) break;
        rep(i, N) cin >> h[i];
        h[N] = 0;
        ll ret = 0;
        stack<int> st;
        

        rep(i,N+1){
            while (!st.empty() && h[st.top()] >= h[i]) {
                int j = st.top();st.pop();
                int L = (st.empty() ? -1 : st.top());
                ret = max(ret, h[j] * (i - L - 1));
            }
            st.emplace(i);
        }
        cout << ret << '\n';
    }


    return 0;
}