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

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

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

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

문제 접근

• 예제에서 주어진 요소를 하나씩 보며 높이별로 구해야 하는 최댓값을 살펴보자.

높이가 1인 직사각형: 가장 작은 값은 1으로 7개의 요소가 모두 공유하기 때문에 길이가 7까지 증가한다.

높이가 2인 직사각형: 2 다음 1이 옴으로써 길이가 1인 직사각형을 구할 수 있다. (다른 높이의 연속을 분할한 너비는 고려하지 않는다. 예시 3*2의 2*2, 4*2의 3*2와 2*2)

높이가 3인 직사각형: 3 다음 3이 연속하여 옴으로써 길이가 2인 사각형을 구할 수 있다.

높이가 4인 직사각형: 4 다음 5 연속하여 옴으로써 길이가 2인 사각형을 구할 수 있다.

높이가 5인 직사각형: 5 다음 1이 옴으로써 길이가 1인 직사각형을 구할 수 있다.

풀이 힌트

• 높이마다 연속된 길이를 구하기 위해 Stack을 이용하였다. 
  • stack을 역삼각형(▽)의 형태로 둔다. 낮은 높이의 요소는 stack의 아래에 둔다.
  • 높이가 유지되고 있기 때문에 자신보다 작은 수를 만나기 전까지 길이 계산을 미룬다.
  • top의 값보다 높은 수는 본인보다 같거나 큰 수를 만나는 경우 길이가 늘어난다.
  • top의 값보다 낮은 수는 top이 가지고 있었던 길이를 유지할 수 있다.
  • top의 값이 낮은 수를 만나 pop될 때 연속된 길이와 높이를 곱하여 너비를 구할 수 있다.

 

• 구체적인 로직은 다음과 같다.
  
  • top의 값이 현재 삽입하려고 하는 값보다 큰 경우 push 한다.
  • top의 값이 현재 삽입하려고 하는 값보다 작은 경우 pop 한다.
  • top의 값이 현재 삽입하려고 하는 값과 같은 경우 top의 길이를 1만큼 증가시킨다.
  • top을 pop 할 때가 중요하다.
    • pop하는 요소의 높이 * 길이와 현재 너비의 최댓값을 비교하여 큰 값을 저장한다.
    • pop하는 요소의 길이를 stack의 top에 더해준다. (높은 요소의 길이를 유지할 수 있으므로)

 

• 이제 stack을 이용하는 과정을 살펴보자.

6
1 3 2 1 1 1

초기값으로 첫 번째 값을 스택에 넣어준다.

 

코드

추가 설명

• stack에 남아있는 값들을 모두 더해주기 위해 N + 1 번을 순회한다.
  • histogram[N]의 값으로 -1을 넣어주었다. 물론 0으로 삽입해도 전혀 문제가 없다.
  • 반복문을 빠져나와서 stack을 비우는 연산을 추가로 진행하는 것과 같은 로직이다.

 

• 입력 조건에 의해 너비의 최대값은  10억 * 10만으로 int 범위를 아득히 넘는다. long long을 사용하자. long long의 최댓값은 9223372036854775807으로 충분히 수용가능하다.
  • 1 ≤ n ≤ 100,000
  • 0 ≤ h ≤ 1,000,000,000

 

• max()를 사용할 때 long long형과 int형을 비교하기 위해서는 캐스팅이 필요하므로 pair의 값 부분(first)을 long long으로 선언해주었다.

 

• 연속된 길이를 저장하기 위해 len 변수를 사용했다.
  • len은 현재 삽입하려는 값의 길이를 구하기 위해 pop한 요소들의 길이를 모두 저장하고 있다.
  • 삽입하려는 요소 또한 길이 1을 가지고 있기 때문에, 삽입하거나 TOP의 길이에 더해줄 때 len + 1 을 더하는 것이다..

#include <bits/stdc++.h>

#define VAL first
#define CNT second
using namespace std;

int histogram[100001];
stack<pair<long long, int> > S;

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

    int N;
    long long mx;
    while (true) {
        cin >> N;
        if (N == 0)
            return 0;
        for (int i = 0; i < N; ++i) {
            cin >> histogram[i];
        }
        mx = 0;
        histogram[N] = -1;
        S = stack<pair<long long, int> >();

        S.push({histogram[0], 1});
        for (int i = 1; i <= N; ++i) {
            int len = 0;
            while (!S.empty() && S.top().VAL > histogram[i]) {
                len += S.top().CNT;
                mx = max(mx, S.top().VAL * len);
                S.pop();
            }
            if (!S.empty() && S.top().VAL == histogram[i])
                S.top().CNT += len + 1;
            else
                S.push({histogram[i], len + 1});
        }
        cout << mx << '\n';
    }
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.