Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

20. 분할 정복

재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.

Java / Python

9. 히스토그램에서 가장 큰 직사각형

6549번

히스토그램에서 가장 큰 직사각형을 찾는 문제. 분할 정복으로도 풀 수 있고, 스택으로 풀 수도 있습니다.

이번 문제는 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하는 문제입니다.

• Java

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

class Main {
	static int[] arr;
	static int N;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		while(true){
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			if(N == 0)
				break;			
			arr = new int[N];
			for(int i=0; i < N; i++)
				arr[i] = Integer.parseInt(st.nextToken());
			System.out.println(getMax(0, N - 1));
		}
	}

	private static long getMax(int left, int right){
		if(left == right) return arr[left];

		int mid = (left + right) / 2;
		// 두 구간으로 나누어, 둘 중 큰 넓이를 반환
		long ret = Math.max(getMax(left, mid), getMax(mid+1, right));

		int start = mid;
		int end = mid+1;
		// mid 기준 양쪽으로 너비 2만큼 겹치는 직사각형
		long height = (long)Math.min(arr[start], arr[end]);
		ret = (long)Math.max(ret, height*2);
		
		// 범위를 벗어나기 전까지 확장
		while(left < start || end < right){
			// 왼쪽 범위를 넘지 않은 경우
			if(left < start && end < right){
				// 높이가 높은 쪽으로
				if(arr[start -1] < arr[end+1])
					height = (long)Math.min(height, arr[++end]);
				else
					height = (long)Math.min(height, arr[--start]);
			}
			else if(left < start){
				// 오른쪽 범위를 넘은 경우 왼쪽으로만 
				height = (long)Math.min(height, arr[--start]);
			}
			else if(end < right){
				// 왼쪽 범위를 넘은 경우 오른쪽으로만 
				height = (long)Math.min(height, arr[++end]);
			}
			ret = Math.max(ret, height*(end-start+1));
		}
		return ret;
	}
}

• Python

import sys

def getMax(l, r):
    if l == r:
        return h[l]
    else:
        mid = (l + r) // 2
        start = mid
        end = mid + 1
        height = min(h[start], h[end])
        tmp = height * 2

        cnt = 2
        while True:
            if (h[start] == 0 or start == l) and (h[end] == 0 or end == r): 
                break 
            elif h[start] == 0 or start == l:
                if h[end + 1] < height:
                    height = h[end + 1]
                end += 1
            elif h[end] == 0 or end == r:
                if h[start - 1] < height:
                    height = h[start - 1]
                start -= 1
            else:
                if h[start - 1] > h[end + 1]:
                    if h[start - 1] < height:
                        height = h[start - 1]
                    start -= 1
                else:
                    if h[end + 1] < height:
                        height = h[end + 1]
                    end += 1
            cnt += 1
            tmp = max(tmp, height * cnt)
        return(max(getMax(l, mid), getMax(mid + 1, r), tmp))  

while True:
    h = list(map(int, sys.stdin.readline().split()))
    if h[0] == 0:
        break
    print(getMax(1, len(h) - 1))