[c++] 백준 6549 히스토그램에서 가장 큰 직사각형 (3가지 풀이)

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

6549번: 히스토그램에서 가장 큰 직사각형

세그먼트 트리와 분할 정복, 스택으로 유명한 문제이다.

제일 간단한 풀이는 스택이며, 시간 복잡도도 O(n)으로 제일 빠르다.

분할정복은 세그먼트 트리를 사용하는 방법과 사용하지 않는 방법이 있는데,

이는 둘 다 O(nlogn)으로 속도는 스택 풀이보다는 느리다.

 

1. 스택 O(n)

스택에는 히스토그램의 인덱스를 저장한다.

히스토그램의 높이가 증가할 때에는 스택에 인덱스를 저장한다.

높이가 감소할 때는 감소한 높이의 사각형이 이전 사각형을 포함하지 못하므로,

높이를 포함할 수 있는 사각형이 나올 때까지 pop 하며, 넓이를 계산해 준다.

 

이 과정을 그림으로 나타내면 다음과 같다.

감소한 직사각형의 인덱스를 idx,

pop 한 직사각형의 인덱스를 cur_idx,

pop한 직사각형의 높이를 h라 하자.

 

pop 할 때마다 계산해주어야 하는 넓이의 수식은 다음과 같다.

(idx - cur_idx) * h

넓이를 계속 계산해 주며, 최댓값을 갱신하면 된다.

 

※주의사항

1. 위에 설명대로만 구현하면, 반복이 다 끝난 후 스택에 남아있는 직사각형들이 있을 수 있다.

   히스토그램을 입력받을 때 1~n까지 받고, 0번과 n+1번 인덱스에는 높이가 0인 직사각형을 넣어주면,

   스택에 직사각형이 남는 것을 막을 수 있다.

2. long long 자료형을 써주어야 한다. 최대 넓이를 계산할 때,

   int 자료형으로는 오버플로우가 발생하므로 주의하자

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

int n;
int hist[100100];
stack<int> stk;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(1){
        cin>>n;
        if(!n) break;
        ll M=0;
        //입력
        for(int i=1; i<=n; i++)
            cin>>hist[i];
        // 히스토그램 틀어막기
        hist[0] = hist[n+1] = 0;
        // 탐색 진행
        for(int i=0; i<=n+1; i++){
            while(!stk.empty() && hist[i] < hist[stk.top()]){
                ll h = hist[stk.top()];
                stk.pop();
                ll l = i;
                if(!stk.empty())
                    l = i-stk.top()-1;
                M = max(M, l*h);
            }
            stk.push(i);
        }
        cout << M << '\n';
    }
    return 0;
}

2. 분할 정복 (세그먼트 트리 사용)

구간 [ l, r ]을 잡고, 그 구간에서의 최솟값을 찾아서, 그곳을 기준으로 분할 정복하면 된다.

구간 [ l, r ]에서의 m에서 최솟값을 가진다 할 때,

[ l, m-1 ]과 [ m+1, r ]로 구간을 다시 잡고, 계산해 주는 것이다.

구간을 새로 잡을 때마다 넓이를 계산해 주고, 최대를 찾아주면 된다.

 

구간의 최솟값을 찾을 때 세그먼트 트리를 사용하고,

세그먼트 트리에는 구간 최솟값의 인덱스를 저장한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9*2;
int n;
int hist[100100];
ll sg[1000001], ans;

int init(int node, int s, int e){
    if(s == e) return sg[node] = s;
    int mid = (s+e)/2;
    int l  = init(2*node,s,mid);
    int r = init(2*node+1,mid+1,e);
    if(hist[l] < hist[r])
        return sg[node] = l;
    else
        return sg[node] = r;
}

int query(int node, int s, int e, int l, int r){
    if(e < l || r < s) return INF;
    if(l <= s && e <= r) return sg[node];
    int mid = (s+e)/2;
    int left_idx  = query(2*node, s, mid, l, r);
    int right_idx = query(2*node+1, mid+1, e, l, r);
    if(left_idx == INF)
        return right_idx;
    else if(right_idx == INF)
        return left_idx;
    else{
        if(hist[left_idx] < hist[right_idx])
            return left_idx;
        else
            return right_idx;
    }
}

void rectangle(ll l, ll r){
    if(l > r)
        return;
    ll m = query(1, 0, n-1, l, r);
    ans = max(ans, hist[m]*(r-l+1));
    rectangle(l, m-1);
    rectangle(m+1, r);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(1){
        cin>>n;
        if(!n) break;
        ans=0;
        //입력
        for(int i=0; i<n; i++)
            cin>>hist[i];
        init(1,0,n-1);
        rectangle(0, n-1);
        cout << ans << '\n';
    }
    return 0;
}

3. 분할 정복 (세그먼트 트리 사용하지 않음)

처음에 [ l, r ]에서 반복문을 돌려 최솟값을 찾고, 그 기준으로 분할 정복을 하려 했으나,

최악에 경우에 O(n^2)이다 라는 게시판의 내용을 보고 포기했었다.

 

그래서 풀이를 찾아보니,

m = (r+l)/2를 정하고 생각해 보면, 3가지 경우가 나온다.

 

1. 구간 [ l, m ]에 넓이가 최대인 직사각형이 있는 경우.

2. 구간 [ m, r ]에 넓이가 최대인 직사각형이 있는 경우.

3. m을 걸쳐서 넓이가 최대인 직사각형이 있는 경우.

 

3을 구할 때에는 m을 기준으로 오른쪽, 왼쪽으로 알맞게 확장해 가면서 구한다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll hist[100100];
ll rectangle(int s, int e){
    ll m = (s+e)/2;
    ll m_area = hist[m], height = hist[m];
    ll l = m-1, r = m+1;
    if(s+1>=e)
        return m_area;
    while(s < l || r < e){
        // l이 더 이상 갈 곳이 없거나
        // r이 갈 곳이 있고, 그곳의 높이가 l의 높이보다 작지 않을 때
        if(s >= l || (r < e && hist[l] <= hist[r])){ 
            height = min(hist[r], height);
            r++;
        }
        else{
            height = min(hist[l], height);
            l--;
        }
        ll width = r-l-1;
        m_area = max(m_area, width*height);
    }
    ll left_area = rectangle(s, m),
       right_area = rectangle(m,e);
    return max(m_area, max(left_area, right_area));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(1){
        int n; cin>>n;
        if(!n) break;
        hist[0] = hist[n+1] = 0;
        for(int i=1; i<=n; i++)
            cin>>hist[i];
        cout << rectangle(0,n+1) << '\n';
    }
    return 0;
}