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

문제 주소 : www.acmicpc.net/problem/6549

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

fast io 미적용

문제 확인

 

특별한 알고리즘이 필요 없는 스택을 이용한 구현 문제입니다. 

 

풀이

 

입력받은 직사각형의 높이와 i 값을 스택에 쌓으면서 기록합니다. 다음 나오는 직사각형의 높이에 따라 다음과 같이 동작합니다.

• 다음 직사각형의 높이에 높다면 계속해서 스택을 쌓아갑니다.
• 높이가 같은 경우 시작 지점인 i값을 기록해 두었으므로 스택에 넣을 필요가 없습니다.
• 다음 직사각형의 높이가 낮다면 스텍에서 만들 수 있는 직사각형만큼 체크를 합니다. 

만들 수 있는 직사각형의 가로길이는 i - idx[top] 이며 높이는 stack[top]입니다. 스택에 기록된 직사각형 들은 오름차순으로 정렬되어 있는 상태이므로 스택 아래에 저장되어 있는 직사각형의 가로길이는 사이에 포함된 직사각형들을 포함할 수 있기 때문에 현재 지점인 i, 높이에 해당하는 막대의 위치 idx[top]과의 차이가 됩니다. 이러한 과정을 stack[top] > h일 때까지 반복합니다.

i=3에서 i=4가 되는 경우 2, 3에 해당하는 히스토그램에서 만들 수 있는 직사각형을 체크하고 스택에서 빼냅니다. 이때 i=4에 해당하는 막대의 h값만 기록해도 되는 이유는 시작 위치가 이미 이전에 기록된 상태이기 때문에 바꿀 필요가 없습니다.

 

모든 탐색이 끝나고 나면 직사각형의 가로 길이는 n - idx[top]이 되며 스택에 남은 막대들을 같은 방식으로 계산합니다.

 

코드

#include <iostream>
using namespace std;
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int stack[100001] = { -1 }, idx[100001], top = 0;
    int n;
    cin >> n;
    while (n) {
        long long max = 0, size;
 
        for (int i = 0, t; i < n; i++) {
            cin >> t;
            if (stack[top] > t) {//다음 직사각형이 작은 경우
                do {
                    size = ((long long)i - idx[top]) * stack[top];
                    max = max < size ? size : max;
                    --top;
                } while (stack[top] > t);//만들 수 있는 직사각형 체크
                if (t)
                    stack[++top] = t;//i값은 남아있는 흔적을 이용하고, h값만 기록
            }
            else if (t && stack[top] < t) {//직사각형이 큰 경우
                stack[++top] = t;
                idx[top] = i;//스텍에 추가
            }
 
        }
        while (top != 0) {//남은 히스토그램 처리
            size = ((long long)n - idx[top]) * stack[top];
            max = max < size ? size : max;
            --top;
        }
        cout << max << '\n';
        cin >> n;
    }
}