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

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

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

문제

히스토그램: 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형
각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수 있음

입력
각 테스트 케이스는 한 줄로 이뤄져 있고, 직사각형 수 n이 가장 처음으로 주어짐 (1 <= n <= 100,000)
히스토그램에 있는 직사각형의 높이인 n개의 정수 h_1, ..., h_n (0 <= h_i <= 1,000,000,000)가 주어짐
(왼쪽부터 오른쪽 순서대로)
모든 직사각형 너비 1, 입력 마지막 줄 0)
출력: 각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이 출력

---

풀이

• `stack`: 인덱스 저장하는 스택
  • 높이가 증가하는 순서로 인덱스 유지
• `max`: 최대 직사각형 넓이

 

• 오른쪽으로 이동하며 스택 처리
  • `height = h[stack.pop()]`: 현재 직사각형 높이는 pop된 막대 높이
  • width: pop된 높이가 확장될 수 있는 구간
    • 왼쪽 경계 = pop 후 `stack.peek() + 1` / 오른쪽 경계 = `i - 1`
    • `(i - 1) - (stack.peek() + 1) + 1` = `i - stack.peek() - 1`
    • IF. 스택이 비었으면 -> 모든 구간 가능 => `i`
• 끝에 도달한 후 스택에 남아 있는 높이 처리

=> 높이가 증가하면 push, 높이가 감소하면 pop하면서 직사각형 계산, 스택 비울 때까지 계산

static long getMax(long[] h) {
    Stack<Integer> stack = new Stack<>();
    long max = 0;
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
            long height = h[stack.pop()];
            long width = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(max, height * width);
        }
        stack.push(i);
    }

    while (!stack.isEmpty()) {
        long height = h[stack.pop()];
        long width = stack.isEmpty() ? n : n - stack.peek() - 1;
        max = Math.max(max, height * width);
    }

    return max;
}

 

---

코드

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

// 히스토그램에서 가장 큰 직사각형
public class boj_6549 {
    static int n;

    static long getMax(long[] h) {
        Stack<Integer> stack = new Stack<>();
        long max = 0;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
                long height = h[stack.pop()];
                long width = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            long height = h[stack.pop()];
            long width = stack.isEmpty() ? n : n - stack.peek() - 1;
            max = Math.max(max, height * width);
        }

        return max;
    }

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

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

            if (n == 0) break;

            long[] h = new long[n];
            for (int i = 0; i < n; i++) {
                h[i] = Long.parseLong(st.nextToken());
            }

            long max = getMax(h);

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

        System.out.println(sb);
    }
}