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

---

www.acmicpc.net/problem/6549

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

---

N이 10만이기때문에 일반적인 모든구간을 탐색하는 N^2풀이시 시간초과를 만나게된다.

 

복잡도를 줄이기위해 어떤 직사각형을 생각해보면

 

그 높이는 입력으로 들어온 것들중 한개일 것이다. 너비는 적당한 구간일 것이고,

 

따라서 높이를 N개 탐색하는데, 구간에 대해서 최솟값을 반환해주는 함수가있다면, 

 

높이를 최소부터 최대까지 탐색할수 있을것이다. 그러면 구간 점 쿼리 문제로 바뀌게 되고

 

세그먼트트리를 통하여 구간의 최솟값을 logN만에 구할 수 있다.

 

즉 문제풀이 단계는 다음과 같다.

 

1 ) 양 끝점을 너비로하고 높이의 최솟값을 높이로하는 긴 직사각형을 선택하고 넓이를 계산한다.

 

2 ) 그 인덱스를 기준으로 좌우를 나누어 좌우의 넓이를 계산하면서 진행한다.

 

재귀함수로 구현할 수 있다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 히스토그램에서가장큰직사각형 {
	public static int n;
	public static long answer = -1;
	public static int []seg;
	public static int h[];
	public static int out = 987654321;
	public static void main(String[] args) throws Exception {
		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;
			h = new int[n+1];
			seg = new int[4*(n+1)];
			for(int i=1 ; i <=n;i++) {
				h[i] = Integer.parseInt(st.nextToken());
			}
			seginit(1,1,n);
			dfs(1,n);
			sb.append(answer+"\n");
			answer = -1;
		}System.out.println(sb);
	}
	private static void dfs(int s, int e) {
		if(e<s)return;
		if(s==e) {
			long res = h[e];
			answer = answer > res ? answer : res;
			return ;
		}
		int index = findmin(1,1,n,s,e);
		long res = (long)(e-(s-1)) * (long)h[index];
		answer = answer > res ? answer : res;
		dfs(s,index-1);
		dfs(index+1,e);
	}
	private static int seginit(int node, int s, int e) {
		if(s==e) return seg[node] = e;
		int l = seginit(2*node, s , (s+e)>>1);
		int r = seginit(2*node+1, ((s+e)>>1)+1, e);
		return seg[node] = h[l] > h[r] ? r : l;
	}
	private static int findmin(int node, int l, int r , int s  , int e) {
		if(r < s || e < l) return out;
		else if( s <= l && r<= e) return seg[node];
		int rr = findmin(2*node, l, (r+l)>>1, s, e);
		int ll = findmin(2*node+1, ((r+l)>>1)+1, r, s, e);
		if(rr==out && ll!= out) return ll;
		if(rr!=out && ll== out) return rr;
		// 둘다 out인경우가? 존재할수 없다
		return h[rr] > h[ll] ? ll : rr ;
	}
}

 

---