울타리 잘라내기 (문제 ID: FENCE, 난이도: 중)

문제 : https://algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

 

 

 

예제 입력

3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2

예제 출력

20
16
8

 

 

public static void main(String[] args) {
    int fenceCount = 7;
    int[] fenceHeight = {7, 1, 5, 9, 6, 7, 3};
    System.out.println(getMaxRectangle(fenceHeight, 0, fenceCount-1)); // 20

    fenceCount = 7;
    fenceHeight = new int[]{ 1, 4, 4, 4, 4, 1, 1 };
    System.out.println(getMaxRectangle(fenceHeight, 0, fenceCount-1)); // 16

    fenceCount = 4;
    fenceHeight = new int[]{ 1, 8, 2, 2 };
    System.out.println(getMaxRectangle(fenceHeight, 0, fenceCount-1)); // 8
}

public static int getMaxRectangle(int[] fenceHeight, int left, int right) {
    // 기저 사례 : 판자가 하나인 경우
    if(left == right) {
        return fenceHeight[left];
    }

    // 분할 기준점 mid 를 중심으로 [left <-> mid],  [mid+1 <-> right] 두 구간으로 분할한다.
    int mid = (left + right) / 2;

    // 분할한 문제를 각개격파
    int maxRectangle = Math.max(getMaxRectangle(fenceHeight, left, mid), getMaxRectangle(fenceHeight, mid+1, right));

    int lo = mid, hi = mid + 1;

    // [mid, mid + 1]만 포함하는 너비 2인 사각형을 고려한다.
    int height = Math.min(fenceHeight[lo], fenceHeight[hi]);
    maxRectangle = Math.max(maxRectangle, height * 2);

    // mid 에서 출발한 lo, hi 가 각각 왼쪽, 오른쪽으로 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
    while(left < lo || hi < right) {
        // 항상 높이가 더 높은 쪽으로 확장한다.
        if(left < lo && (hi == right || fenceHeight[lo - 1] > fenceHeight[hi + 1])) {
            --lo;
            height = Math.min(height, fenceHeight[lo]);
        } else {
            ++hi;
            height = Math.min(height, fenceHeight[hi]);
        }
        // 확장한 후 사각형의 넓이
        maxRectangle = Math.max(maxRectangle, height * (hi - lo + 1));
    }


    return maxRectangle;
}