[백준 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이 하나 주어진다.
문제 풀기 전 설계
문제를 처음 봤을 때부터 스택을 이용해야 할 것 같다는 생각이 들었다.
[백준 2493] https://www.acmicpc.net/problem/2493
[백준 6198] https://www.acmicpc.net/problem/6198
이런 문제들과 유사해보였기 때문이다.
스택을 이용한다면 고려해야 할 점은 두 가지가 있다.
1. 어떤 기준으로 스택에 넣을 것인가?
2. 어떤 방법으로 넓이를 구할 것인가?
이 점을 중심으로 코드를 작성하면 될 것이다.
문제 코드(스택)
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class BOJ_6549_Stack {
static int n;
static long[] num;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
String s;
while (!(s = br.readLine()).equals("0")) {
Stack<Integer> stack = new Stack<>();
st = new StringTokenizer(s);
n = Integer.parseInt(st.nextToken());
num = new long[n];
for (int i = 0; i < n; i++) num[i] = Long.parseLong(st.nextToken());
long maxArea = 0;
for (int i = 0; i < n; i++) {
/*
이전 높이보다 현재 높이가 작거나 같은 경우
현재 높이보다 작은 이전 높이들을 pop하면서 넓이를 구한다
*/
while ((!stack.isEmpty()) && num[stack.peek()] >= num[i]) {
long height = num[stack.pop()];
/*
다음으로 pop 하는 인덱스의 높이는 현재 pop한 높이보다 반드시 낮으므로
너비는 i부터 다음 pop 할 인덱스 전까지가 된다
스택에 값이 없다면 1 ~ i이므로 i가 된다
*/
long weight = (stack.isEmpty()) ? i : (i - stack.peek() - 1);
maxArea = Math.max(maxArea, height * weight);
}
stack.push(i);
}
/*
스택에 값이 남은 경우가 있으므로 위의 과정을 한 번 더 수행한다
*/
while (!stack.isEmpty()) {
long height = num[stack.pop()];
long weight = (stack.isEmpty()) ? n : (n - stack.peek() - 1);
maxArea = Math.max(maxArea, height * weight);
}
sb.append(maxArea).append('\n');
}
System.out.println(sb);
}
}문제 코드(세그먼트 트리)
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_6549_SegmentTree {
static int n;
static long[] num;
static int[] tree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
String s;
while (!(s = br.readLine()).equals("0")) {
st = new StringTokenizer(s);
n = Integer.parseInt(st.nextToken());
num = new long[n + 1]; // 세그먼트 트리를 쉽게 이용하기 위해 인덱스는 1부터 시작
for (int i = 1; i <= n; i++) num[i] = Long.parseLong(st.nextToken());
// 트리 사이즈를 구하는 과정
int exponent = (int) Math.ceil(Math.log(n) / Math.log(2)) + 1;
int treeSize = (int) Math.pow(2, exponent);
tree = new int[treeSize];
init(1, n, 1);
sb.append(findMaxArea(1, n)).append('\n');
}
System.out.println(sb);
}
/*
(start ~ end) 범위 내에서 최대 넓이를 구하는 메소드
넓이 = 높이 * 너비이므로 최소 높이를 기준으로 양 옆으로 탐색하며 최대값을 갱신한다
*/
private static long findMaxArea(int start, int end) {
int mid = findMinHeight(1, n, 1, start, end);
long area = (end - start + 1) * num[mid];
// 최소 높이 인덱스 왼쪽에 막대가 있는 경우
if (start <= mid - 1) {
// 해당 범위에서 최대 넓이를 구해 비교
long temp = findMaxArea(start, mid - 1);
area = Math.max(area, temp);
}
// 최소 높이 인덱스 오른쪽에 막대가 있는 경우
if (end >= mid + 1) {
// 해당 범위에서 최대 넓이를 구해 비교
long temp = findMaxArea(mid + 1, end);
area = Math.max(area, temp);
}
return area; // 범위 내에서 가장 큰 값 리턴
}
/*
(start ~ end) 범위 내에서 가장 작은 높이를 가진 인덱스를 찾는 메소드
기초적인 세그먼트 트리와는 다르게 비교값(높이)과 리턴값(인덱스)이 다르므로 과정이 좀 추가되었다
*/
private static int findMinHeight(int start, int end, int node, int left, int right) {
if (right < start || end < left) return -1;
if (left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
int mLeft = findMinHeight(start, mid, node * 2, left, right);
int mRight = findMinHeight(mid + 1, end, node * 2 + 1, left, right);
if (mLeft == -1) return mRight;
if (mRight == -1) return mLeft;
return (num[mLeft] > num[mRight]) ? mRight : mLeft;
}
/*
세그먼트 트리를 초기 세팅하는 메소드
세그먼트 트리에 저장될 값은 (start ~ end) 범위 내에서 가장 작은 높이를 가진 인덱스
*/
private static int init(int start, int end, int node) {
if (start == end) return tree[node] = start;
int mid = (start + end) / 2;
int left = init(start, mid, node * 2);
int right = init(mid + 1, end, node * 2 + 1);
return tree[node] = (num[left] > num[right]) ? right : left;
}
}문제 풀이
자세한 풀이는 주석을 통해 이해하면 될 것 같다.
스택을 이용한 풀이에서 중요한 점은 위에서 설계했던 것처럼
- 어떤 기준으로 스택에 넣을 것인가?
- 어떤 방법으로 넓이를 구할 것인가?
두 가지를 고려해야 한다.
세그먼트 트리를 이용한 풀이에서 중요한 점은
기본적인 세그먼트 트리와 다르게 트리에 저장된 값(인덱스)과 저장하는 기준(높이)가 다르다는 것이다.
Review
세 번째로 풀게 된 플레티넘 문제이다. 풀기 전에는 스택을 이용하는 문제라고만 생각했지만 세그먼트 트리를 이용해서 풀 수 있다는 것이 신기했다. 세그먼트 트리를 응용해서 푼 첫 문제라 더 의미가 있다.
