[BAEKJOON] 6549 히스토그램에서 가장 큰 직사각형

문제 요약

• 알고리즘 분류: 분할정복, 스택, 세그먼트 트리
• 난이도:  Platinum5
• 문제내용:
  •  각 케이스마다 위 그림 처럼 히스토그램 넓이중 가장 큰것을 구해라.
• 사이트 : https://www.acmicpc.net/problem/6549

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

문제풀이

   이번에는 문제 유형은 분할 정복, 스택, 세그먼트 트리 3가지 방법으로 풀수 있다. 간단하게 완전탐색으로도 답은 나오지만 문제는 주는 데이터의 수가 10만이다. 10만으로 O(N^2)으로 풀기에는 너무 무리가 있다. 저 문제 통과할라면 O(NlogN)으로 풀어야 답이나오기 때문에  어렵지만 위에 3가지 방법으로 풀어야 된다.

일단 먼저 분할 정복을 설명한 뒤에 스택, 세그먼트 트리 푸는 방법을 설명하겠다. 

1. 분할 정복

 분할 정복방법으로 접근 방법은 범위를 정해서 중간으로 해서 양쪽으로 늘리면서 최대 넓이를 구할 예정이다.

 위 그림은 예제를 가고온것을 그린것이다. 위 그림이고 왼쪽, 오른쪽 범위에서 큰 넓이를 구한다고 가정해보자.

중간은 2,3 인덱스이다. 범위 안에 탐색하는 기준은 우선 높이가 큰것 부터해서 오른쪽으로 이동할지 왼쪽으로 이동할지는 알아서 정하면 되지만 오른쪽으로 이동한다고 보자 그러면 1, 4번째중 오른쪽기준으로 4번째 1, 5번째는 5번째가 높이가 더 높아서 5번째 그 다음에는 1번째 이동하는 식으로 하면된다. 그러면 탐색해도 큰 넓이 순서 로 움직일수가 있다. 그렇게 하면 전체에서 중간으로 쪼개면 O(logN)시간이 나오고 범위안에 가장큰 넓이 찾는것은 O(N)시간이 나온다.

 그러면 제일 중요한 부분은 큰 넓이 순서대로 움직이는 것인데.. 그 부분 구현은 아래 코드를 보면 된다.

Python

while (l < lmid or rmid < r):
    if(rmid < r and ((lmid <= l) or (heights[lmid - 1] < heights[rmid + 1]))):
        rmid += 1
        height = min(height, heights[rmid])
    else:
        lmid -= 1
        height = min(height, heights[lmid])
    area = max(area, height * (rmid - lmid + 1))

Java

while(l < lmid || rmid < r) {
    // 넓이 큰 순서대로 탐색한다.
    if(rmid < r && ((lmid <= l) || (heights[lmid - 1] < heights[rmid + 1]))) {
        rmid++;
        height = Math.min(height, heights[rmid]);
    }else {
        lmid--;
        height = Math.min(height, heights[lmid]);
    }
    area = Math.max(area, height * (long) (rmid - lmid + 1));
}

 위 코드를 보면 처음에는 이해가 안되는데...  l < lmid || rmid < r 코드는 루프는 양쪽 끝까지 탐색한다고 보면되고 

rmid < r && ((lmid <= l) || (heights[lmid - 1] < heights[rmid + 1])) 이 코드는 끝 부분 비교보면 더 큰쪽으로 이동하는 것이고 그 외는 왼쪽 끝까지 간다음 오른쪽 끝까지 간다고 보면 된다.  위 코드가 분할정복 푸는데 핵심이니 이해하고 전체 코드를 보기를 바란다.  그리고 이해가 안되면 질문을 올려주시면 답변을 드리니 이 부분은 대충 넘어가지 말자!!!

정리

1.  현재 범위 기준으로 반으로 쪼개서 양쪽중 가장 큰 넓이 가져온다.
2.  이전 탐색한 값부터 해서 범위안에  중간 부터 시작해서 가장 큰 넓이를 구한다.
   • 중간으로 부터해서 + or - 1부터 시작한다.
   • 중간으로 탐색한 범위중 높이가 가장 낮은것 *  범위 한해서 이전 탐색한것이랑 비교한다.
   • 이동은하는데 우선 높이가 큰 곳부터 이동한다.
3. 다 탐색될때 까지 1,2 번 반복한뒤 가장 큰 넓이를 구한다.

Code

python

import sys
input = sys.stdin.readline

def solution(l, r):
    global heights
    if(l == r): return heights[l]
    mid = (r + l) // 2
    # 반반 쪼개서 가장 큰 부분을 가져온다.
    area = max(solution(l, mid), solution(mid + 1, r))
    lmid  = mid
    rmid = mid + 1
    height = min(heights[lmid], heights[rmid])

    # 이전 구한 값과 중간 위치의 넓이를 비교해서 가장 큰 것은 가져 온다.
    area = max(area, height * 2, heights[lmid], heights[rmid])
    while (l < lmid or rmid < r):
        if(rmid < r and ((lmid <= l) or (heights[lmid - 1] < heights[rmid + 1]))):
            rmid += 1
            height = min(height, heights[rmid])
        else:
            lmid -= 1
            height = min(height, heights[lmid])
        area = max(area, height * (rmid - lmid + 1))
    return area

while 1:
    N, *heights = map(int, input().split())
    if  N == 0: break
    print(solution(0, N - 1))

Java

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

public class Main {

	static long[] heights;
	
	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());
			int N = Integer.parseInt(st.nextToken());
			if(N == 0) break;
			heights = new long[N];
			for(int i = 0; i < N; i++) {
				heights[i] = Long.parseLong(st.nextToken());
			}
			System.out.println(solution(0, N - 1));
		}
	}
	
	public static long solution(int l, int r) {
		if(l == r) return heights[l];
		
		int mid = (r + l) /2;
		int lmid = mid;
		int rmid = mid + 1;
		long area = Math.max(solution(l, lmid), solution(rmid, r));
		long height = Math.min(heights[lmid], heights[rmid]);
		area = Math.max(area, height * 2);
		while(l < lmid || rmid < r) {
			// 넓이 큰 순서대로 탐색한다.
			if(rmid < r && ((lmid <= l) || (heights[lmid - 1] < heights[rmid + 1]))) {
				rmid++;
				height = Math.min(height, heights[rmid]);
			}else {
				lmid--;
				height = Math.min(height, heights[lmid]);
			}
			area = Math.max(area, height * (long) (rmid - lmid + 1));
		}
		return area;
	}
}