문제
히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제이다. 히스토그램은 각각 너비 1인 직사각형 막대들로 구성된다.
입력
여러 테스트 케이스로 구성되며, 각 줄에 n과 n개의 정수 h1, ..., hn이 주어진다. (1 ≤ n ≤ 100,000, 0 ≤ hi ≤ 1,000,000,000) n이 0이면 입력을 종료한다.
출력
각 테스트 케이스마다 최대 직사각형의 넓이를 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0 | 8 4000 |
풀이
스택을 이용한 O(N) 알고리즘으로 해결한다. (코드는 스택 방식으로 구현됨)
- 스택에 인덱스를 저장하며, 높이가 증가하면 push
- 현재 막대 높이가 스택 top보다 작거나 같으면, 스택에서 pop하며 직사각형 넓이 계산
- 꺼낸 막대의 높이 =
histogram[stack[top]] - 너비 = 스택이 비었으면
i, 아니면i - 1 - stack[top(남은)]
- 꺼낸 막대의 높이 =
- 최대 넓이를 갱신한다
- 루프 종료 후 스택에 남은 막대들도 같은 방식으로 처리
핵심 아이디어: 스택에 단조 증가 순서로 인덱스를 관리하여, 각 막대가 높이 기준 직사각형의 최소 높이가 되는 범위를 O(1)에 계산한다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day162BOJ6549분할정복 { // 6549 분할정복 구
public static int[] histogram;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int N;
while (true) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
if (N == 0) {
break;
}
histogram = new int[N];
for (int i = 0; i < N; i++) {
histogram[i] = Integer.parseInt(st.nextToken());
}
sb.append(getArea(N)).append('\n');
histogram = null;
}
System.out.println(sb);
br.close();
}
public static long getArea(int len) {
int[] stack = new int[len];
int sSize = 0;
int top = -1;
long maxArea = 0;
for (int i = 0; i < len; i++) {
while (sSize > 0 && histogram[stack[top]] >= histogram[i]) {
int height = histogram[stack[top--]];
sSize--;
long width = sSize == 0 ? i : i - 1 - stack[top];
maxArea = Math.max(maxArea, height * width);
}
stack[++top] = i;
sSize++;
}
while (sSize > 0) {
int height = histogram[stack[top--]];
sSize--;
long width = sSize == 0 ? len : len - 1 - stack[top];
maxArea = Math.max(maxArea, width * height);
}
return maxArea;
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)