백준 6549번 히스토그램에서 가장 큰 직사각형 c++ 풀이

문제

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

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

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

예제 입력 1 복사

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

예제 출력 1 복사

8
4000

 

이전에 풀이한 히스토그램이랑 입력만 다르고 동일한 문제이다.

하지만 예전에 풀이한 풀이법이 기억나지 않아서 답지를 참고했다. 플레티넘은 아직 나에게 너무 어려운 듯 하다. 

그래도 계속해서 어려운 문제에 도전하다 보면 실력이 늘지 않을까한다.

 

문제의 로직

1. 입력을 모두 받아준다.

2. 히스토그램의 왼쪽부터 오른쪽까지 탐색을 진행한다.

3. 히스토그램이 비어있거나 현재 막대기가 스택의 가장 최근 막대기의 높이보다 더 크다면 스택에 값을 넣어준다.

4. 스택이 비어있지 않거나 스택의 가장 최근 막대기의 높이보다 현재 막대기의 높이가 더 작다면 while문을 돌린다. 현재 막대기의 높이보다 스택의 가장 최근 막대기의 높이가 더 크다면 모두 pop을 해 준다.

5. pop된 막대기는 넓이를 계산하여 가장 큰 값을 저장해 준다. (스택의 가장 최근 막대기의 높이 * (현재 막대기의 인덱스 - 가장 최근 막대기의 인덱스))

6. 스택이 비거나 현재 막대기의 높이보다 가장 최근 스택 막대기의 높이가 더 작거나 같아진다면 while문을 종료한다.

7. 모두 끝난 후 스택이 비어있지 않다면 히스토그램의 끝부분 부터 돌면서 다시 반복해주며 가장 큰 값을 저장해 준다.

 

- c++ 풀이 (풀이 참고 : https://cloer.tistory.com/211)

#include <iostream>
#include <stack>
#define ll long long
using namespace std;

struct rect {int idx, h;};
ll max(ll a, ll b) {return a > b ? a : b;}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        int n; cin >> n;
        if(n == 0) break;
        stack<rect> S;
        ll ans = 0;
        for(int i = 0; i < n; i++) {
            int h, idx = i; cin >> h;
            while(!S.empty() && S.top().h > h) {
                idx = S.top().idx;
                ans = max(ans, (ll)S.top().h * (i - idx));
                S.pop();
            }
            if(S.empty() || S.top().h < h)
                S.push({idx, h});
        }
        while(!S.empty()) {
            ans = max(ans, (ll)S.top().h * (n - S.top().idx));
            S.pop();
        }
        cout << ans << '\n';
    }
}