문제
이해
임의의 히스토그램에서 만들 수 있는 직사각형 중에 가장 큰 값을 출력하면 됩니다.
접근
가장 먼저 n의 범위가 눈에 들어왔습니다. n은 최대 10만이기 때문에 시간복잡도 N^2으로는 불가능합니다. 시간복잡도는 NlogN 혹은 N으로 줄이는 것이 문제의 핵심입니다.
히스토그램에서 만들 수 있는 직사각형의 특징은 높이는 직사각형을 이루는 히스토그램의 부분 직사각형 높이로 제한되어 있다는 것입니다. 따라서, 직사각형을 만들때는 히스토그램의 일부를 정하고 좌우를 보면서 너비가 어디까지 확장될 수 있는지 확인하면 됩니다.
위 방법에 대해 시간복잡도를 분석해봅시다. 모든 부분 직사각형 n을 좌우 n-1만큼 탐색해야 합니다. 따라서 시간복잡도는 n^2입니다. 하지만 만일 좌우 탐색시에 현재 높이보다 작은 직사각형을 만나면 더 이상 너비를 확장시킬 수 없기 때문에 탐색을 종료해도 됩니다. 모든 직사각형을 탐색할 필요가 없기 때문에 시간복잡도는 n^2보다 작아보이지만 최악의 경우 즉, 모든 직사각형의 높이가 같은 경우에는 n^2에 수렴합니다.
최악의 경우에 대해서 어떻게 하면 시간복잡도를 줄일 수 있을까요? 저는 백트래킹과 같이 가지를 치는 방법을 떠올렸습니다. 모든 직사각형의 높이가 같은 경우 어느 직사각형을 잡고 탐색을 돌리든 항상 같은 경우를 탐색하는 것과 같습니다. 따라서, 탐색의 중복을 없애는 방법을 생각했습니다.
우선, 직사각형을 어디서부터 탐색하면 가지를 칠 수 있을지 생가했습니다. 직사각형을 입력 순서대로 탐색하기에는 가지치기가 의미 없어보입니다. 따라서, 정렬을 한 뒤 가장 높이가 낮은 직사각형부터 탐색하는 방법을 떠올렸습니다. (n은 최대 10만이기 때문에 정렬이 가능합니다.) 낮은 직사각형부터 탐색한 이유는 다음의 보다 큰 직사각형을 탐색할 때 항상 좌우의 끝은 이전에 탐색한 현재보다 높이가 낮은 직사각형으로 떨어지기 때문입니다.
그렇다면 탐색했던 직사각형의 정보를 저장하는 자료구조가 필요합니다. 자료구조의 선택조건은 1. 동적으로 저장될 것, 2. 위치를 기준으로 정렬될 것.. 입니다. pool 방식을 이용해도 되겠지만 저는 좌우 한계선을 빨리 찾기 위해 lower, upper를 지원하는 TreeSet을 사용했습니다.
여기까지 정리해봅시다.
1. 직사각형을 높이 기준으로 오름차순 정렬
2. 정렬된 직사각형을 차례로 탐색 (탐색 시에는 자신보다 낮은 직사각형의 자료구조를 참고)
3. 탐색이 끝나면 자료구조에 직사각형 정보를 저장
하지만 여기서 끝내면 모든 높이가 같은 최악의 경우에는 시간복잡도를 그다지 줄이지 못합니다. 따라서, 만일 좌우 한계선에 있는 직사각형이 현재의 직사각형과 같으면 한계선에 있는 직사각형의 너비를 가져옵니다. 이는 DP와 같이 이전에 탐색한 데이터를 가져옵니다. (이전에 탐색한 직사각형은 현재 직사각형을 포함하기 떄문입니다.)
풀이
private static void Solve(Rect rect) {
int lowerIdx = -1;
int upperIdx = n;
Rect lower = rectSet.lower(rect);
Rect upper = rectSet.higher(rect);
if (lower != null) {
lowerIdx = lower.idx;
}
if (upper != null) {
upperIdx = upper.idx;
}
if (lower != null && lower.height == rect.height) {
rectSet.add(rect);
rect.size = lower.size;
max = Math.max(max, rect.size);
return;
}
if(upper != null && upper.height == rect.height){
rectSet.add(rect);
rect.size = upper.size;
max = Math.max(max, rect.size);
return;
}
rect.size = (long)rect.height * (upperIdx - lowerIdx - 1);
rectSet.add(rect);
max = Math.max(max, rect.size);
}각 직사각형에서 수행될 탐색 메소드입니다.
하한과 상한을 -1, n으로 두고 각 조건에 대해서 수정합니다. 하한과 상한이 존재하면 그에 대한 값으로 수정합니다. 하지만 하한과 상한에 존재하는 직사각형이 현재와 같다면 경계선의 직사각형의 너비를 그대로 가져오고 메소드를 종료합니다.
하한과 상한에 같은 높이 직사각형이 없다면 너비와 현재 높이를 통해 넓이를 구하고 갱신합니다.
코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static StringBuilder sb = new StringBuilder();
static StringTokenizer st = null;
static Rect[] diagrams;
static TreeSet<Rect> rectSet;
static long max;
static int n;
public static void main(String[] args) throws IOException {
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("ps_solution/src/input/input6549.txt")));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
if (n == 0) {
break;
}
max = 0;
rectSet = new TreeSet<>((Rect o1, Rect o2) -> o1.idx - o2.idx);
diagrams = new Rect[n];
for (int i = 0; i < n; i++) {
diagrams[i] = new Rect(Integer.parseInt(st.nextToken()), i, i);
}
Arrays.sort(diagrams);
for (int i = 0; i < n; i++) {
Solve(diagrams[i]);
}
sb.append(max).append("\n");
}
System.out.println(sb.toString());
}
private static void Solve(Rect rect) {
int lowerIdx = -1;
int upperIdx = n;
Rect lower = rectSet.lower(rect);
Rect upper = rectSet.higher(rect);
if (lower != null) {
lowerIdx = lower.idx;
}
if (upper != null) {
upperIdx = upper.idx;
}
if (lower != null && lower.height == rect.height) {
rectSet.add(rect);
rect.size = lower.size;
max = Math.max(max, rect.size);
return;
}
if(upper != null && upper.height == rect.height){
rectSet.add(rect);
rect.size = upper.size;
max = Math.max(max, rect.size);
return;
}
rect.size = (long)rect.height * (upperIdx - lowerIdx - 1);
rectSet.add(rect);
max = Math.max(max, rect.size);
}
static class Rect implements Comparable<Rect> {
int height;
int idx;
long size;
public Rect(int height, int idx, long size) {
this.height = height;
this.idx = idx;
this.size = size;
}
@Override
public int compareTo(Rect o) {
return this.height - o.height;
}
}
}결과
추가
본 문제의 분류는 세그먼트 트리, 분할 정복으로 되어 있습니다. 따라서, 위 풀이는 정석적인 풀이가 아닙니다. 이런 풀이도 있다라는 참고로만 봐주시면 감사하겠습니다.
