OJ
[BOJ] 6549 히스토그램에서 가장 큰 직사각형 (JAVA)
P3PP4
2023. 1. 10. 10:00
https://www.acmicpc.net/problem/6549
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
세그먼트 트리로 해결할 수 있는 문제입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static final int INF = Integer.MAX_VALUE;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N;
static int[] input, result;
public static void main(String[] args) throws Exception {
while(true) {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
if(N == 0) break;
input = new int[N + 1];
result = new int[N * 4];
for (int i = 1; i <= N; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
make(1, N, 1);
sb.append(get(1, N)).append("\n");
}
System.out.print(sb.toString());
}
static int select(int startIndex, int endIndex, int treeIndex, int startRange, int endRange) {
if(endIndex < startRange || endRange < startIndex) return INF;
if(startRange <= startIndex && endIndex <= endRange) return result[treeIndex];
int midIndex = (startIndex + endIndex) / 2;
int left = select(startIndex, midIndex, treeIndex * 2, startRange, endRange);
int right = select(midIndex + 1, endIndex, treeIndex * 2 + 1, startRange, endRange);
if(left == INF) return right;
else if(right == INF) return left;
return input[left] < input[right] ? left : right;
}
static long get(int startIndex, int endIndex) {
long maxWidth = 0;
int minIndex = select(1, N, 1, startIndex, endIndex);
maxWidth = (long) (endIndex - startIndex + 1) * (long) input[minIndex];
if(startIndex <= minIndex - 1) maxWidth = Math.max(maxWidth, get(startIndex, minIndex - 1));
if(minIndex + 1 <= endIndex) maxWidth = Math.max(maxWidth, get(minIndex + 1, endIndex));
return maxWidth;
}
static int make(int startIndex, int endIndex, int treeIndex) {
if(startIndex == endIndex) return result[treeIndex] = startIndex;
int midIndex = (startIndex + endIndex) / 2;
int left = make(startIndex, midIndex, treeIndex * 2);
int right = make(midIndex + 1, endIndex, treeIndex * 2 + 1);
return result[treeIndex] = input[left] < input[right] ? left : right;
}
}