울타리 잘라내기

풀이

무식하게 풀기

우선은 무식하게 푸는 방법을 생각해봅시다. 사각형의 넓이는 가장 왼쪽 판자와 가장 오른쪽 판자를 무엇으로 할 것이냐에 따라 달라집니다. 가장 왼쪽 판자를 $l$, 가장 오른쪽 판자를 $r$, 각 판자 높이의 배열을 $h[]$ 라고 했을 때, 사각형의 넓이는 다음과 같습니다.
$(r-l+1)\times \min_{i=l}^{r}h[i]$
따라서 모든 l과 r을 순회하여 얻은 사각형의 넓이 중 최댓값을 구하면 됩니다.

import java.util.*;

public class Main {

    // 각 판자의 높이를 담은 배열입니다.
    public static int[] fenceHeight;
    // 답입니다.
    public static int result = 0;

    // 값을 입력받는 함수입니다.
    public static void input(Scanner scanner) {
        int fenceCount = scanner.nextInt();
        fenceHeight = new int[fenceCount];
        for (int i = 0; i < fenceCount; i++) {
            fenceHeight[i] = scanner.nextInt();
        }
    }
    // 문제를 해결하는 함수입니다
    public static void solve() {
        for (int left = 0; left < fenceHeight.length; left++) {
            int minHeight = fenceHeight[left];
            for (int right = left; right < fenceHeight.length; right++) {
                minHeight = Math.min(minHeight, fenceHeight[right]);
                result = Math.max(result, (right - left + 1) * minHeight);
            }
        }
    }
    // 답을 출력하는 함수입니다.
    public static void output() {
        System.out.println(result);
        result = 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

하지만 문제에서 입력의 최대 크기는 20,000이므로 $O(n^2)$ 시간이 걸리는 이 알고리즘으로 해결하기 힘듭니다. 따라서 분할 정복 알고리즘을 사용해 풀 계획을 세우겠습니다.

분할 정복 알고리즘의 설계

분할 정복 알고리즘을 설계하려면 분할 정복 알고리즘의 구성 요소를 어떻게 만들어야할지 생각하는 것이 좋습니다.
우선 문제를 어떻게 분할할지를 결정해야 합니다. $n$개의 판자를 절반으로 나눠 두 개의 부분 문제를 만듭시다. 그러면 우리가 찾는 최대 직사각형은 다음 세 가지 중 하나에 속할 것입니다.

• 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다.
• 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.
• 가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.

이때 첫 번째와 두 번째 경우는 반으로 나눈 부분 문제를 재귀 호출하여 해결할 수 있습니다. 우리는 가장 큰 사각형의 넓이를 찾고 있기 때문에 이 중 더 큰 것을 항상 택하면 됩니다. 그리고 세 번째 경우의 답을 구하면 됩니다.

양쪽 부분 문제에 걸친 경우의 답

양쪽 부분 문제에 모두 걸치는 직사각형 중 가장 큰 것을 찾는 방법을 떠올리기 쉽지 않습니다. 답을 찾는 힌트는 이 직사각형은 반드시 부분 문제 경계에 있는 두 판자를 포함한다는 것입니다. 따라서 부분 문제 경계에 있는 두 판자를 시작으로 양쪽으로 퍼져나가며 직사각형의 넓이를 비교해서 가장 큰 직사각형의 넓이를 찾아야 합니다. 그러기 위해 양쪽으로 퍼져나가는 순서를 정해야 합니다. 그냥 왼쪽, 오른쪽 번갈가아며 포함한다면 항상 직사각형의 넓이는 가장 높이가 낮은 판자에 의해 결정되는데 높이가 더 낮은 판자부터 포함한다면 높이가 더 높은 판자를 포함했을 때도 가장 낮은 판자의 높이는 변하지 않기 때문에 더 넓은 직사각형의 넓이를 비교할 기회가 사라집니다. 따라서 양쪽으로 퍼질 때는 왼쪽 판자와 오른쪽 판자 중 더 높이가 높은 판자를 포함해서 직사각형을 만들고 비교하고 다음에도 이 과정을 반복합니다.

    // h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환합니다.
    public static int solve(int left, int right) {
        // 기저 사례: 판자가 하나밖에 없는 경우
        if (left == right) return fenceHeight[left];
        // [left, mid], [mid + 1, right]의 두 구간으로 문제를 분할한다.
        int mid = (left + right) / 2;
        // 분할한 문제를 각개격파
        int result = Math.max(solve(left, mid), solve(mid + 1, right));
        // 부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
        int lo = mid, hi = mid + 1;
        int height = Math.min(fenceHeight[lo], fenceHeight[hi]);
        // [mid, mid + 1]만 포함하는 너비 2인 사각형을 고려한다.
        result = Math.max(result, height * 2);
        // 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
        while (left < lo || hi < right) {
            // 항상 높이가 더 높은 쪽으로 확장한다.
            if (hi < right && (lo == left || fenceHeight[lo - 1] < fenceHeight[hi + 1])) {
                hi++;
                height = Math.min(height, fenceHeight[hi]);
            } else {
                lo--;
                height = Math.min(height, fenceHeight[lo]);
            }
            // 확장한 후 사각형의 넓이
            result = Math.max(result, height * (hi - lo + 1));
        }
        return result;
    }

분할 정복 알고리즘을 구현한 코드입니다.

정당성 증명

이 알고리즘의 정당성을 보이려 할 때 핵심이 되는 부분은 양쪽 부분 문제에 걸쳐 있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳음을 보이는 부분입니다. 이것은 귀류법을 이용해 쉽게 증명할 수 있습니다.
어떤 사각형 $R$이 우리가 구현한 과정을 통해 찾은 최대 직사각형보다 더 크다고 가정해 봅시다. 우리는 너비가 2인 사각형에서 시작해서 한 칸씩 사각형의 너비를 늘려가므로, 우리가 고려한 사각형들 중 $R$과 너비가 같은 사각형이 반드시 하나 있습니다. 두 개는 없습니다. 이 사각형을 $R'$라고 합시다. 너비가 같으므로 $R$이 더 넓기 위해서는 높이가 반드시 $R'$보다 높아야 합니다. 즉 $R$의 판자들의 높이는 $R'$의 판자들 중 가장 높이가 낮은 판자 $A$보다 높아야 합니다. 하지만 그럴 수 없습니다. 왜냐하면 우리는 양쪽 판자를 비교하고 더 높이가 높은 판자를 선택했기 때문입니다. $A$와 다른 판자 중 $A$가 아닌 판자를 선택했다는 말은 $A$보다 더 낮은 판자를 선택했다는 뜻이고 $R'$의 높이는 $A$였는데 더 낮은 판자가 선택된다면 $R'$보다 작을 수 밖에 없습니다. 따라서 양쪽 부분 문제에 걸쳐 있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳습니다.

시간 복잡도 분석

우리가 구현한 코드는 주어진 $n$ 크기의 배열을 $n\over 2$ 크기의 배열 두 개로 나눈 뒤 이들을 각각 해결합니다. 재귀 호출 외에 함수 내에서 하는 일은 두 부분에 걸쳐 있는 사각형을 찾는 작업밖에 없으므로, 이 작업의 시간 복잡도가 전체 시간 복잡도를 결정합니다. 이 과정은 너비가 2인 사각형에서 시작해서 너비가 $n$인 사각형까지를 하나하나 검사하므로 시간 복잡도는 $O(n)$이 됩니다.
재귀 호출의 깊이가 같은 작업들의 모든 비교하는 작업의 양은 처음 $n$에 비례합니다. 그리고 재귀 호출을 할 때 $n$의 크기가 절반씩 줄어듦으로 $\log n$ 깊이까지 내려갑니다. 따라서 이 분할 정복 알고리즘은 병합 정렬과 같은 시간 복잡도 $O(n\log n)$을 갖습니다.

회고

다른 풀이

스위핑 알고리즘을 사용하면 분할 정복을 이용할 때보다 더 빠른 $O(N)$ 시간에 해결할 수 있습니다.

구현

import java.util.*;

public class Main {

    // 각 판자의 높이를 담은 배열입니다.
    public static int[] fenceHeight;
    // 답입니다.
    public static int result;

    // 값을 입력받는 함수입니다.
    public static void input(Scanner scanner) {
        int fenceCount = scanner.nextInt();
        fenceHeight = new int[fenceCount + 1];
        for (int i = 0; i < fenceCount; i++) {
            fenceHeight[i] = scanner.nextInt();
        }
        fenceHeight[fenceCount] = 0;
    }
    // 스택을 사용한 O(n) 해법
    public static void solve() {
        // 남아 있는 판자들의 위치들을 저장한다.
        Stack<Integer> remaining = new Stack<>();

        result = 0;
        for (int i = 0; i < fenceHeight.length; i++) {
            // 남아 있는 판자들 중 오른쪽 끝 판자가 h[i]보다 높다면
            // 이 판자의 최대 사각형은 i에서 끝난다.
            while (!remaining.empty() && fenceHeight[remaining.peek()] >= fenceHeight[i]) {
                int j = remaining.pop();
                int width = -1;
                // j번째 판자 왼쪽에 판자가 하나도 안 남아 있는 경우 left[j]=-1.
                // 아닌 경우 left[j]=남아 있는 판자 중 가장 오른쪽에 있는 판자의 번호가 된다.
                if (remaining.empty())
                    width = i;
                else
                    width = i - remaining.peek() - 1;
                result = Math.max(result, fenceHeight[j] * width);
            }
            remaining.push(i);
        }
    }
    // 답을 출력하는 함수입니다.
    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고

솔직히 어려워서 스위핑 알고리즘은 따로 공부해야겠습니다. 잘 이해가 안됩니다.