히스토그램에서 가장 큰 직사각형 BOJ 6549 java 풀이

문제 분석

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

문제 풀이

무식하게 풀기

🌝 무식하게 풀 수 있는가? - brute force 방법 이용

모든 right과 left를 다 찾아 가장 큰 넓이를 뽑아내면 된다!

사각형의 넓이는 (right-left+1)*min(height)로 계산할 수 있다.

 

package DivideandConquer;

import java.io.BufferedReader;
import java.util.Scanner;

import static java.lang.Math.max;
import static java.lang.Math.min;

public class BOJ6549 {
    static int num;
    static int right;
    static int left;
    static int result = 0;
    static int[] height;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while(true) {
            num = scanner.nextInt();
            if (num==0) break;
            height = new int[num];
            for (int i = 0; i < num; i++) {
                height[i] = scanner.nextInt();
            }
            System.out.println(divide(height));
        }

    }
    static int divide(int[] height){
        int length = height.length;
        for(left=0;left<length;left++){
            int minHeight = height[left];
            for(right=left; right<length; right++){
                minHeight = min(minHeight, height[right]);
                result = max(result, (right - left + 1) * minHeight);
            }
        }
        return result;
    }

}

 

하지만 이 방법의 경우 시간복잡도가 n^2이라 해당 문제를 시간안에 풀 수 없음.

분할 정복으로 풀기

🔥실행 시간을 줄이기 위해 분할정복 사용!

1️⃣ 분할 정복시 사각형이 생성되는 경우는 총 3가지

1. 가운데를 기준으로 오른쪽 영역에 넓이가 최대인 사각형이 있는 경우

2. 가운데를 기준으로 왼쪽 영역에 넓이가 최대인 사각형이 있는 경우

3. 경계선에 걸쳐 사각형이 있는 경우

 

📝 1번과 2번의 경우 반으로 문제를 나눠서 그냥 그대로 계산하면 되고,

      3번의 경우 "반드시 부분 문제의 경계에 있는 두 판자를 포함"하고 왼쪽, 오른쪽 판자 중 더 높은 판자를 선택해 확장!

 

2️⃣ 분할 정복의 경우, 재귀 함수를 사용하므로 기저 사례 설정과 반복 기준 설정이 필요.

기저 사례: 사각형 판자가 1개밖에 없을 때 바로 height return (문제에서 너비는 항상 1이라고 했음!)

반복 기준: 3번 부분 문제가 입력 전체를 덮을 때까지!

 

3️⃣ 겹쳐있는 사각형의 계산

1. 경계선에 있는 두 사각형은 항상 포함되므로, 두 사각형을 선택하는 변수 lo, hi 설정

2. 두 사각형이 재귀 범위, 즉 right랑 left안에서 항상 높이가 더 높은 쪽으로 확장할 수 있도록 설정

3. 계산한 것 중 가장 큰 넓이 retrun

 

package DivideandConquer;

import java.io.BufferedReader;
import java.util.Scanner;

import static java.lang.Math.max;
import static java.lang.Math.min;

public class BOJ6549 {
    static int num;
    static int[] height;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while(true) {
            num = scanner.nextInt();
            if (num==0) break;
            height = new int[num];
            for (int i = 0; i < num; i++) {
                height[i] = scanner.nextInt();
            }
            System.out.println(divide(0,height.length-1));
        }

    }
    static int divide(int left, int right){
        //기저 사례: 판자 1개일때
        if(left==right){
            return height[left];
        }

        //오른쪽이나 왼쪽 사각형 각개격파
        int mid = (right + left) / 2;
        int result = max(divide(left, mid), divide(mid+1, right));

        //걸쳐진 사각형 계산
        //lo, hi 설정
        int lo = mid;
        int hi = mid + 1;
        int minHeight = min(height[lo], height[hi]);
        //mid와 mid+1만 포함하는 사각형 넓이 고려!
        result = max(result, minHeight * 2);

        //left와 right 범위 안에 있을 때 모든 경우 스캔
        while (lo > left || hi < right) {

            //right 쪽으로 확장할 경우
            if (hi < right && (lo == left || height[lo - 1] < height[hi + 1])) {
                hi++;
                minHeight = min(minHeight, height[hi]);
            }
            else {
                lo--;
                minHeight = min(minHeight, height[lo]);
            }
            //확장 후 사각형 넓이
            result = max(result, minHeight * (hi - lo + 1));
        }

        return result;
    }

}