[BaekJoon] 6549번 - 히스토그램에서 가장 큰 직사각형 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제로 단조 스택을 활용해서 해결할 수 있다.

아래는 예제 그림의 히스토그램이다. 히스토그램의 첫 번째 막대부터 순서대로 탐색을 진행한다.

먼저 첫 번째 막대의 경우 기준이 될 다른 막대가 없다.

두 번째 막대의 경우 첫 번째 막대보다 높이가 낮다. 이전 막대보다 높이가 낮을 경우 이전 막대의 높이를 높이로 갖는 직사각형은 이어서 등장할 수 없다. 이전 막대의 높이를 높이로 갖는 직사각형의 넓이를 구해준다.

이전 막대의 높이를 이용해 후보 직사각형을 구했으면 해당 높이는 이제 필요가 없다. 두 번째 막대는 첫 번째 막대보다 높이가 낮으므로 두 번째 막대의 높이를 높이로 갖는 직사각형은 첫 번째 막대부터 여전히 등장할 수 있어서 첫 번째 막대의 높이를 두 번째 막대와 같게 생각해준다.

세 번째 막대의 경우 두 번째 막대보다 높이가 높다. 세 번째 막대의 높이를 높이로 갖는 최대 직사각형이 이후 등장할 수 있으니 넘어간다.

네 번째 막대의 경우 세 번째 막대보다 높이가 높다. 네 번째 막대의 높이를 높이로 갖는 최대 직사각형이 이후 등장할 수 있으니 넘어간다.

다섯 번째 막대의 경우 네 번째 막대보다 높이가 낮다. 네 번째 막대의 높이를 높이로 갖는 최대 직사각형은 이어서 등장할 수 없으니 네 번째 막대의 높이를 높이로 갖는 직사각형의 넓이를 구해준다.

이어서 세 번째 막대도 다섯 번째 막대보다 높이가 낮아서 세 번째 막대의 높이를 높이로 갖는 최대 직사각형도 이어서 등장할 수 없다. 막대들이 오름차순을 유지하니 세 번째 막대와 네 번째 막대의 넓이를 한 변으로 하는 직사각형도 만들 수 있다.

두 번째 막대는 다섯 번째 막대와 높이가 동일하니 탐색을 종료한다. 세 번째 막대와 네 번째 막대의 높이를 다섯 번째 막대와 맞춰준다.

여섯 번째 막대의 높이는 다섯 번째 막대보다 높으니 넘어가고,

일곱 번째 막대의 높이는 여섯 번째 막대와 동일하니 넘어간다. 이렇게 모든 막대에 대해 한번씩 비교를 해줬다.

모든 막대의 길이가 오름차순이니 마지막으로 가능한 직사각형을 구해준다.

모든 경우에 대해 탐색을 완료했다.

그림에서는 높이를 낮추는 것으로 표현하긴 했는데 실제로는 단조 스택에 막대의 높이와 막대의 등장 위치를 같이 저장해줬다. 직사각형의 높이는 막대의 높이로, 너비는 현재 위치와 막대의 등장 위치의 차로 구할 수 있다. 현재 막대의 높이가 단조 스택의 top에 있는 막대보다 낮으면 막대를 꺼내서 최대 직사각형의 넓이를 구해주고 현재 막대의 등장 위치를 꺼냈던 막대의 등장 위치로 갱신해주면 된다.

모든 막대에 대해 탐색을 완료했으면 스택에는 오름차순으로 일부 막대의 높이와 위치가 저장되는데 이것도 꺼내서 최대 직사각형의 넓이를 갱신해주면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            if (n == 0) break;

            Deque<int[]> stack = new ArrayDeque<>();
            long max = 0;

            for (int i = 0; i < n; i++) {
                int h = Integer.parseInt(st.nextToken());
                int idx = i;

                while (!stack.isEmpty() && stack.peek()[0] > h) {
                    max = Math.max(max, (long) (i - stack.peek()[1]) * stack.peek()[0]);
                    idx = stack.pop()[1];
                }

                stack.push(new int[]{h, idx});
            }

            while (!stack.isEmpty()) {
                max = Math.max(max, (long) (n - stack.peek()[1]) * stack.peek()[0]);
                stack.pop();
            }

            sb.append(max).append("\n");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#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;

        stack<pair<int, int>> st;
        long long mx = 0;

        for (int i = 0; i < n; i++) {
            int h;
            cin >> h;
            int idx = i;

            while (!st.empty() && st.top().first > h) {
                mx = max(mx, 1LL * (i - st.top().second) * st.top().first);
                idx = st.top().second;
                st.pop();
            }

            st.push({h, idx});
        }

        while (!st.empty()) {
            mx = max(mx, 1LL * (n - st.top().second) * st.top().first);
            st.pop();
        }

        cout << mx << '\n';
    }
}

---