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

문제 설명

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

 

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

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

 

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

 

 

- 그냥 단순히 히스토그램에서 가장 넓이가 큰 직사각형을 구하면 된다.

 

문제 풀이

처음에는 3가지 case를 분류했다.

당장 다음 높이가 stack의 top보다 큰경우, 같은경우, 작은경우로 나누어서 처리했었다.

 

1. 큰 경우?

- 스택에 있는 모든 사각형의 넓이를 + 1해준다.

- 새로운 높이가 추가된다. push({height,1})

 

2. 같은 경우

- 모두 길이 + 1

 

3. 작은 경우

- 스택에 있는 큰애들은 다 지워버린다.

- 여태 가로길이만큼 새로 push.

 

그래서 아래 코드가 나왔다. 논리적으로도 약간 모순이 있을거같은데 일단 시간초과로 실패했다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (true) {
        int n;
        long long ans = 0;
        cin >> n;
        if (n == 0) break;

        stack<pair<long long, long long>> s; //height, 가로 넓이;
        for (int i = 0; i < n; i++) {
            long long height;
            cin >> height;
            if (s.empty()) { // 비었을 때
                s.push({height, 1});
                ans = max(ans, 1 * height);
                continue;
            }

            if (height < s.top().first) {
                int cur = s.top().second;
                ans = max(ans, s.top().first * s.top().second);
                s.pop();
                s.push({height, cur + 1}); // 가로의 넓이의 + 1와 좀전에 받은 높이.
                ans = max(ans, s.top().first * s.top().second);
            }

            // 같은 높이
            else if (s.top().first == height) {
                int cur = s.top().second;
                s.pop();
                s.push({height, cur + 1}); // 가로 +1 해주기
                ans = max(s.top().first * s.top().second, ans);
            }

            // 더 높은게 들어온 경우...
            else {
                stack<pair<long long, long long>> t;
                while (!s.empty()) {
                    if(s.top().first > height){
                        s.pop();
                        continue;
                    }
                    t.push({s.top().first, s.top().second + 1}); // 원래 있던거 +1 해서 넣어주기.
                    s.pop();
                }
                while (!t.empty()) {
                    s.push(t.top());
                    ans = max(s.top().first * s.top().second, ans);
                    t.pop();
                }
                // 새로운거 추가.
                s.push({height, 1});
            }
        }
        cout << ans << '\n';
    }

}

 

코드도 너무 길고 답도 없다.

 

조금 관점을 바꿔야했다.

 

1. 모든 높이를 순회하며 스택에 인덱스를 저장하자.  (인덱스를 알면 높이도 자연스레 알 수 있다.)
2. 현재 높이가 스택의 top에 저장된 것보다 작을 경우에는 stack에서 pop하여 해당 높이의 최대 넓이를 계산하자.
   • 이때 스택의 top 다음 인덱스부터 현재 인덱스까지의 거리가 넓이가 된다.

이렇게 되면 시간 복잡도도 O(n)으로 확실히 줄어듦을 알 수 있다.

 

애초에 스택에 든 것의 전제는 아직 넓이가 끊기지 않은 놈들이다. 즉 for문에서 i가 상태라고 할 때, i상태에서 아직 끊기지 않은 사각형들이기에 굳이 width를 둘 필요도 없고, 넓이 계산에 있어서 width의 시작점을 고민하는 낭비를 제거할 수 있었다.

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        vector<int> heights(n);
        for (int i = 0; i < n; i++) cin >> heights[i];

        stack<int> s;
        long long max_area = 0;
        
        for (int i = 0; i <= n; i++) {
            // 현재 높이 처리
            int h = (i == n) ? 0 : heights[i];
            
            while (!s.empty() && heights[s.top()] > h) {
                int height = heights[s.top()];
                s.pop();
                
                int width;
                if (s.empty()) {
                    width = i;
                } else {
                    width = i - s.top() - 1;
                }
                
                max_area = max(max_area, (long long)height * width);
            }
            
            s.push(i);
        }

        cout << max_area << '\n';
    }
    return 0;
}

 

확연히 반복되는 스택 연산이 줄어들어 나름 괜찮아졌다.

 

 

어렵다...