Platinum V 난이도의 C++로 작성된 문제입니다. 주어진 히스토그램에서 가장 큰 직사각형의 넓이를 찾는 문제입니다.

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

Platinum V 난이도의 C++로 작성된 문제입니다. 주어진 히스토그램에서 가장 큰 직사각형의 넓이를 찾는 문제입니다.

문제 소개

백준 6549번 "히스토그램에서 가장 큰 직사각형"은 n개의 막대로 이루어진 히스토그램이 주어졌을 때, 이 히스토그램 안에서 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 문제입니다. 입력은 0으로 끝나며, 각 테스트 케이스마다 히스토그램의 막대 개수와 각 막대의 높이가 주어집니다.

문제 번호: 6549
문제명: 히스토그램에서 가장 큰 직사각형
난이도: Platinum V
사용 언어: C++
실행 시간: 24 ms
메모리: 4492 KB

접근 방법

이 문제는 히스토그램에서 가장 큰 직사각형을 찾는 고전적인 문제입니다. 직관적으로는 모든 가능한 직사각형을 고려하여 최대 넓이를 찾을 수 있지만, 이는 시간 복잡도가 매우 높아 효율적이지 않습니다.

가장 효율적인 접근 방법은 스택(Stack) 자료구조를 활용하는 것입니다. 스택을 이용하면 각 막대를 기준으로 그 막대를 포함하면서 가장 넓은 직사각형을 효율적으로 찾을 수 있습니다.

왜 스택을 사용했는가?
스택을 사용하면 현재 막대보다 높이가 낮거나 같은 이전 막대들을 효율적으로 관리할 수 있습니다. 막대를 순회하면서 스택에 막대의 인덱스를 저장하는데, 만약 현재 막대의 높이가 스택의 가장 위에 있는 막대(이전 막대)보다 낮다면, 스택의 가장 위 막대는 현재 막대보다 왼쪽으로는 스택의 두 번째 막대, 오른쪽으로는 현재 막대까지를 왼쪽/오른쪽 경계로 하는 직사각형의 높이가 될 수 있습니다. 이 정보를 바탕으로 직사각형의 넓이를 계산하고 최대값을 갱신할 수 있습니다.

풀이 과정

입력 처리:
- 히스토그램의 막대 개수 n을 입력받습니다.
- n이 0이면 프로그램을 종료합니다.
- n개의 막대 높이를 std::vector<long long> histogram에 저장합니다.
스택 초기화 및 센티널 추가:
- 스택 barStack을 선언하여 막대의 인덱스를 저장합니다.
- maxRectangle 변수를 0으로 초기화하여 최대 넓이를 저장합니다.
- 알고리즘의 편의를 위해 히스토그램의 끝에 높이 0인 막대를 추가합니다 (histogram.push_back(0); n++;). 이는 스택에 남아있는 모든 막대들을 처리할 수 있도록 돕는 센티널(Sentinel) 역할을 합니다.
히스토그램 순회 및 스택 활용:
- currentBarIndex를 0부터 n (센티널 포함)까지 순회합니다.
- while 루프: 스택이 비어있지 않고, 현재 막대의 높이(histogram[currentBarIndex])가 스택의 가장 위에 있는 막대 높이(histogram[barStack.top()])보다 작으면 다음을 수행합니다.
  - 스택에서 가장 위의 막대 인덱스를 poppedBar_idx로 가져옵니다.
  - poppedBar_idx에 해당하는 막대의 높이(height = histogram[poppedBar_idx])를 가져옵니다.
  - poppedBar_idx 막대를 기준으로 왼쪽 경계(leftBoundary_idx)를 결정합니다. 스택이 비어있으면 왼쪽 경계는 -1 (맨 왼쪽)이고, 그렇지 않으면 스택의 새로운 top()이 왼쪽 경계의 바로 오른쪽 인덱스가 됩니다.
  - 직사각형의 너비(width)를 계산합니다. 너비는 (currentBarIndex - 1) - leftBoundary_idx 입니다. 현재 막대 바로 앞까지의 범위를 고려합니다.
  - 계산된 직사각형의 넓이(area = height * width)를 maxRectangle과 비교하여 더 큰 값으로 갱신합니다.
- push: while 루프가 끝나면 (현재 막대가 스택의 top보다 높거나 같아지면), 현재 막대의 인덱스(currentBarIndex)를 스택에 푸시합니다.
결과 출력:
- 모든 막대 순회가 끝나면 maxRectangle에 저장된 최대 넓이를 출력합니다.

핵심 아이디어

스택을 이용해 현재 막대를 기준으로 이전 막대들의 최대 직사각형 넓이를 효율적으로 계산합니다. 스택에는 현재까지 고려된 막대들의 인덱스가 오름차순으로 저장되며, 이는 곧 높이가 증가하는 순서를 의미합니다. 현재 막대의 높이가 스택의 top 막대보다 낮을 때, 스택의 top 막드는 현재 막대 이전에서 자신보다 높이가 낮거나 같은 가장 가까운 막대(왼쪽 경계)와 현재 막대(오른쪽 경계) 사이에서 가장 큰 직사각형을 만들 수 있는 후보가 됩니다.

주의할 점

센티널(Sentinel)의 중요성: 히스토그램 끝에 높이 0인 막대를 추가하는 것은 매우 중요합니다. 이것이 없으면, 마지막에 스택에 남아있는 막대들을 처리하지 못하게 됩니다.
폭(Width) 계산: 폭을 계산할 때 currentBarIndex - 1을 사용하는 것은 현재 막대를 제외하고 그 직전까지를 너비로 보기 위함입니다. leftBoundary_idx는 스택에서 pop한 후의 새로운 top()의 인덱스이며, 이것이 바로 해당 막대의 왼쪽 경계를 나타냅니다.
높이가 같은 막대: 높이가 같은 막대가 연속될 경우, 현재 막대가 스택의 top 막대와 높이가 같으면 while 루프에 진입하지 않고 push 됩니다. 이는 동일 높이의 막대가 길게 이어질 때, 가장 큰 직사각형의 너비를 올바르게 계산하기 위함입니다.

코드 설명

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

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

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

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

        stack<int> barStack;
        long long maxRectangle = 0;

        // 센티널(Sentinel) 역할을 하는 높이 0인 막대를 히스토그램 끝에 추가
        histogram.push_back(0);
        n++;

        // 각 막대를 순회하며 최대 직사각형 넓이 계산
        for (int currentBarIndex = 0; currentBarIndex < n; currentBarIndex++) {
            // 현재 막대가 스택의 top 막대보다 작으면, 스택의 top 막대를 pop하고 넓이 계산
            while (!barStack.empty() && histogram[barStack.top()] > histogram[currentBarIndex]) {
                int poppedBar_idx = barStack.top(); // pop할 막대의 인덱스
                barStack.pop();

                long long height = histogram[poppedBar_idx]; // pop한 막대의 높이
                // 왼쪽 경계: 스택이 비어있으면 -1 (맨 왼쪽), 아니면 스택의 새로운 top 인덱스
                int leftBoundary_idx = barStack.empty() ? -1 : barStack.top();
                // 폭: 현재 막대의 바로 앞자리까지의 범위
                long long width = (currentBarIndex - 1) - leftBoundary_idx;
                long long area = height * width; // 직사각형의 넓이
                maxRectangle = max(maxRectangle, area); // 최대 넓이 갱신
            }
            // 현재 막대의 인덱스를 스택에 push
            barStack.push(currentBarIndex);
        }

        cout << maxRectangle << "\n";
    }

    return 0;
}

/*
질문 핵심 답변 종합 정리

0. 스택의 탑의 높이보다 현재 막대의 높이가 작을 때만 while 진입. 아니면 현재 막대는 스택에 푸시
1. 스택에는 히스토그램 인덱스만 저장, 높이는 pop 시 popped Bar idx로 참조.
2. 연쇄 pop: 현재 막대보다 높은 막대가 연속이면 pop마다 폭 계산 + 면적 계산 → maxRectangle 갱신.
3. 폭 계산: (currentBarIndex - 1) - leftBoundary_idx
   - 왼쪽 경계 idx는 스택 원래 상태에서 한번 팝된 두번째 높은 막대의 인덱스이므로 히스토그램에서 원래 탑 막대의 전 칸이다
   그대로 currentBarIndex의 전 칸에서 빼면 폭이 나온다. 팝한 뒤의 탑이기 때문에 이미 탑의 인덱스 - 1이 된 셈이다.
   - 현재 낮은 막대(currentBarIndex) 제외. 정확히는 그 막대의 바로 앞자리까지가 폭이니 - 1
4. 왼쪽 경계(leftBoundary_idx) = pop 후 스택 top
5. 높이가 같은 막대를 current bar로 만나는 경우는 pop 안 됨
7. 센티널 0 덕분에 마지막까지 스택에 남은 막대 처리 가능.
6. 1 3 5 5 1의 경우 센티널 0이 마지막에 붙어서 0을 만나면 스택은 [0,4] -> 높이로는 [1,1] 인 상태에서
   0에 의해 연달아 팝되면서 폭이 0,4 기반으로 계산되어 결국엔 첫, 마지막 1도 센티널에 의해 넓이가 계산된다.
8. 연쇄 pop 시 각 pop마다 넓이 계산 후 max 갱신
   → 높이가 같은 막대가 앞 방향으로 이어져도 다 계산하고 그 중 최대값만 남기니
   -> 높이가 같은 막대가 최대한 이어지는 경우의 넓이만 max로 남음.
9. 폭 계산에 왼쪽 경계는 인덱스만 필요, 높이는 신경 안 써도 됨.
10. 시간 복잡도: O(n) → 각 막대 최대 1번 push, 1번 pop
11. 공간 복잡도: O(n) → 스택 최대 n개
12. 에지 케이스:
    - 모든 높이 0, 중간에 하나만 높은 경우, 사인/코사인 형태, 급격한 높이 변동 등 모두 처리 가능
*/

복잡도 분석

시간 복잡도: O(n)
히스토그램의 각 막대는 스택에 최대 한 번 푸시되고, 최대 한 번 팝됩니다. 센티널을 포함하여 총 n+1번의 막대를 순회하며, 각 막대에 대해 스택 연산(push, pop, top)은 상수 시간(O(1))이 걸립니다. 따라서 전체 시간 복잡도는 O(n)입니다.
공간 복잡도: O(n)
스택은 최악의 경우 히스토그램의 모든 막대 인덱스를 저장할 수 있습니다 (예: 막대 높이가 점점 증가하는 경우). 따라서 공간 복잡도는 O(n)입니다.

배운 점

이 문제를 풀면서 가장 크게 배운 점은 스택을 활용하여 "이전/이후의 가장 가까운 작은 값" 또는 "이전/이후의 가장 가까운 큰 값"을 찾는 문제에 효율적으로 접근할 수 있다는 것입니다. 특히 히스토그램에서 가장 큰 직사각형 문제는 이 원리가 아주 잘 적용되는 대표적인 예시였습니다.

또한, 센티널(Sentinel) 패턴을 활용하는 기법을 익혔습니다. 배열이나 시퀀스의 끝에 특별한 값(이 경우 높이 0)을 추가함으로써, 반복문의 마지막 조건을 별도로 처리하거나 스택에 남아있는 요소들을 처리하는 복잡성을 줄일 수 있습니다. 이는 알고리즘 구현을 간결하고 안정적으로 만드는 데 큰 도움이 됩니다.

이 문제에서 사용된 스택 기반 알고리즘은 다양한 문제에 적용될 수 있으며, 특히 동적 계획법(DP)이나 그리디 알고리즘으로 접근하기 어렵거나 비효율적인 경우에 대한 대안으로 고려해볼 만합니다.