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

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

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

stack을 이용하는 문제입니다. 

 

다양한 풀이들이 많이 있는 문제로 유명하다고 하는데, 다른 방식들을 또 알게되면 추가해 보도록 하겠습니다.

 

우선 문제부터 간단하게 요약하면, 

그림과 같이 히스토그램이 위치할 때, 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제입니다. 

이 때, 직사각형의 수는 10만개 까지, 그리고 각각의 높이는 0부터 10억까지 가능합니다. 

 

<Solution>

start 직사각형 결정, end 직사각형을 결정해 내부의 넓이를 찾는 로직을 사용하게 된다고 생각해봅시다. 

 

이 때, start를 고르는 경우의 수가 대략 10만가지, end를 고르는 경우의 수도 대략 10만가지 이므로 O(N^2) 의 로직에서 N 값이 10만으로 불가능합니다. 

다른 방식을 생각해야 합니다. 

 

우선 기본 로직부터 설명하고, 이 로직이 나오게 된 이유도 설명해 보겠습니다.

1. 만약 이전의 원소가 현재보다 작다면, stack에 담는다. (stack은 오름차순 일 것임) 2. 만약 더 작은 원소가 등장하게 된다면 2-1. stack에서 해당 원소보다 큰 것들을 모두 빼면서 넓이를 계산해준다. 2-2. 작은 원소를 다시 넣어서 stack을 오름차순으로 유지한다.

이 로직이 아직은 이해가 안 될 것 같은데 천천히 풀어서 설명해 보겠습니다. 

그림으로 나타내면 다음과 같습니다.

step1을 보면, 처음 stack에는 index 1이 들어가고 해당하는 index의 높이는 2이고 이전보다 작지 않으므로 넣습니다.

이 때, 아직 넓이를 결정할 수 없다고 되어 있는데, 그 이유는 저 높이를 가장 왼쪽 끝으로 하는 직사각형의 넓이를 아직 결정할 수 없기 때문입니다. 오른쪽에 만약 높이 3 등으로 더 높은 히스토그램이 들어오면, 최대 직사각형의 넓이가 더 커질 것이기 때문입니다.

 

마찬가지로 step2, 3에서도 넓이를 결정할 수 없습니다.

 

하지만 step4에서 stack에 이전보다 더 작은 값이 들어왔습니다. 이 때, index 4로 들어온 높이 1짜리 히스토그램으로 인해 앞의 index들 (높이가 1보다 큰) 에 해당하는 히스토그램을 직사각형의 가장 왼쪽 끝으로 하는 최대 넓이들이 구해지게 됩니다. 

 

이렇게 stack을 관리해주며 사각형의 넓이를 갱신해나가는 방식으로 코드를 진행하면 됩니다. 총 한번의 scan으로 문제를 해결하므로 O(N)의 시간복잡도로 문제를 해결할 수 있습니다.

 

실제 구현은 아래와 같습니다. 가장 마지막에는 항상 0짜리 히스토그램을 추가로 넣어주어 stack이 모두 pop되며 계산될 수 있도록 하였습니다.

 

#include <iostream>
#include <stack>

using namespace std;
int N;//히스토그램수
int H[100000+10];//히스토그램 높이
bool InputData() {
    cin >> N;
    if (N == 0) return false;
    
    for (int i=1; i<N+1; i++){
        cin >> H[i];
    }
    H[N+1] = 0;
    return true;
}

long long solution(){
    long long ret=0;
    stack <int> stk;
    stk.push(0);
    
    for(int i = 1; i<N+2; i++){ // 마지막은 길이 0 기둥

        while(stk.size() > 1 && H
        [stk.top()]>H[i]){
            int tmp = H[stk.top()];
            stk.pop();

            ret = max(ret, (long long)tmp * (long long)(i-stk.top()-1));
        }
        stk.push(i);
    }
    return ret;
    
}

int main() {
    long long ans = -1;
    while(InputData()){//입력받는 부분

        //여기서부터 작성
        ans = solution();

        cout << ans << "\n";//출력하는 부분
    }
    return 0;
}