[백준(Baekjoon)][자바(java)] 6549 : 히스토그램에서 가장 큰 직사각형 / 분할 정복

 

https://www.acmicpc.net/problem/6549

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

 

< 문제 풀이 >

 

1.  완전 탐색  ( 브루트 포스 : brute force )   

 

 -->  시간 초과

long ret = 0; int h_min;
for( int left = 0; left < n; left++ ) {
	for( int right = left; right < n; right++ ) {
		h_min = Math.min( h[left], h[right] );
		ret = Math.max( ret, (right-left+1)*h_min );
	}
}

 

 

2.  분할 정복  ( Divide and Conquer )

 

-  [ left, mid ], [ mid+1, right ] 두 구간으로 문제 분할  -- recursion 호출
 ( left와 right가 같으면 그 인덱스의 높이값을 리턴하고 recursion 종료 )

-  분할 한 왼쪽 구간, 오른쪽 구간에서 각각 가장 큰 사각형을 찾음

-  분할 한 것을 합칠 때, 가장 큰 사각형이 가운데에 걸쳐있을 수 있으므로 [ mid, mid+1 ] 만 포함하는 너비 2인 사각형 고려

-  사각형을 확장해나감. 항상 높이가 더 높은 쪽으로. 기존의 가장 큰 사각형과 비교하여 더 큰 값이 정답이 됨

 

입력값 예)

7 2 1 4 5 1 3 3

( 위의 모든 그림은 직접 만든 것임 -- hyunji cho )

 

import java.util.Scanner;

public class Main {
	
	static int h[];
	
	public static long findMaxArea( int left, int right ) {
		
		if( left == right ) return h[left];
		
		int mid = ( left + right ) / 2;
		long ret = Math.max( findMaxArea( left, mid ), findMaxArea( mid+1, right ) );
		
		int lo = mid, hi = mid+1;
		long height = Math.min( h[lo], h[hi] );
		ret = Math.max( ret, height*2 );
		
		while( left < lo || hi < right ) {
			if( hi < right && ( lo == left || h[lo-1] < h[hi+1] ) ) {
				++hi;
				height = Math.min( height, h[hi] );
			}
			else {
				--lo;
				height = Math.min( height, h[lo] );
			}
			ret = Math.max( ret, height*(hi-lo+1) );
		}

		return ret;
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();

		while( sc.hasNext() ) {

			int n = sc.nextInt();
			if( n == 0 ) break;

			h = new int[n];
			for( int i = 0; i < n; i++ )
				h[i] = sc.nextInt();

			sb.append( findMaxArea( 0, n-1 ) + "\n" );
		}

		System.out.println( sb );
		sc.close();
	}
}

( 코드 참고 : 알고리즘 문제 해결 전략 )

 

 

3.  스택  ( Stack )

 

-  각 높이가 담긴 배열 h 을 루프를 돌며 왼쪽부터 차례로 탐색
   스택이 비었으면 현재 인덱스 값을 스택에 넣고, 
   스택이 비어있지 않으면서 스택의 top 인덱스의 높이가 현재 높이보다 크면 pop하여 넓이를 구함

-  모두 탐색 후 스택에 남아있는 인덱스들을 pop하여 넓이를 구하며 최댓값 구함

 

 

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack;

		while( sc.hasNext() ) {

			stack = new Stack<>();
			int n = sc.nextInt(), i, idx;
			if( n == 0 ) break;
			int h[] = new int[n];
			for( i = 0; i < n; i++ )
				h[i] = sc.nextInt();
			long ret = 0, len;

			for( i = 0; i < n; i++ ) {
				while( !stack.empty() && h[i] < h[stack.peek()] ) {
				      idx = stack.pop();
				      len = i;
				      if( !stack.empty() )
					  		len -= stack.peek() + 1;
				      ret = Math.max( ret, h[idx]*len );
				}
				stack.push( i );
			}
			while( !stack.empty() ) {
				idx = stack.pop();
				len = n;
				if( !stack.empty() ) 
					len -= stack.peek() + 1;
				ret = Math.max( ret, h[idx]*len );
			}

			sb.append( ret + "\n" );
		}

		System.out.println( sb );
		sc.close();
	}
}

( 코드 참고 : https://yangorithm.tistory.com/165 )