[백준] 6549번 - 히스토그램에서 가장 큰 직사각형 (Platinum 5)

문제 링크

백준 6549번 - 히스토그램에서 가장 큰 직사각형 (Platinum 5)

문제 설명

주어진 히스토그램에 들어가는 가장 큰 직사각형의 넓이를 구한다.
직사각형의 수 n은 100,000개 이하이며, 직사각형의 높이는 1,000,000,000 이하이다.

정답 코드 및 설명

단계별로 풀어보기에서 분할 정복 항목에 있던 문제라, 분할 정복을 활용하였다.
절반으로 나눈다는 발상까진 혼자 할 수 있었는데, 중간에 걸치는 경우의 처리가 어려웠다.
중간에 걸치는 경우를 처리하는 방법은 검색해서 알고리즘을 이해한 후 사용하였다.

방식은 투포인터와 그리디를 동시에 사용하는 것이다. 구체적으로는 아래와 같다.

1. 경계에 있는 두 점을 투포인터의 시작으로 한다.
2. 너비를 1 늘릴때, 높이가 적게 줄어드는 포인터를 이동시킨다.
3. 포인터의 높이가 줄어든다면, 줄어든 포인터를 높이로 하고, 줄어들지 않는다면 기존 높이를 유지한다.
4. 높이 * 너비로 구한 넓이를 기존의 최댓값과 비교한다.

이 알고리즘의 시간 복잡도를 계산해보자.
직사각형의 수가 N이라면, 중간에 걸치는 경우의 처리에는 시간 복잡도 $O(N)$이 소요된다.
직사각형의 수가 N일 때 걸리는 시간을 $T(N)$이라 하면, $T(2N) = 2*T(N) + O(N)$이다.
따라서 $T(N) = O(N \log N)$임을 알 수 있다.(증명은 생략)

참고로, 단순한 반복문을 사용할 경우 $O(N^2)$으로 해결이 되는데, 이는 시간 초과이다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        while (true) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            if (n == 0)
                break;
            int h[] = new int[n];
            for (int i = 0; i < n; i++)
                h[i] = Integer.parseInt(st.nextToken());
            sb.append(largest(h, 0, n)).append('\n');
        }
        bw.write(sb.toString());
        bw.close();
    }

    static long largest(int h[], int start, int end) {
        if (start + 1 == end)
            return h[start];
        // 중간에 걸친 경우의 처리
        int midIndex = (start + end) / 2;
        // 시작 높이
        long height = h[midIndex - 1] > h[midIndex] ? h[midIndex] : h[midIndex - 1];
        long largest = height * 2;
        // i : 왼쪽 포인터, j : 오른쪽 포인터
        int i = midIndex - 1, j = midIndex;
        while (j - i + 1 < end - start) {
            // 포인터의 높이가 줄어드는 경우
            if (j + 1 < end && (i == start || h[j + 1] >= height)) {
                if (h[j + 1] < height)
                    height = h[j + 1];
                j++;
            } else if (i > start && (j + 1 == end || h[i - 1] >= height)) {
                if (h[i - 1] < height)
                    height = h[i - 1];
                i--;
            // 기존 높이가 유지되는 경우
            } else if (h[i - 1] >= h[j + 1]) {
                height = h[i - 1];
                i--;
            } else {
                height = h[j + 1];
                j++;
            }
            // 넓이 비교
            if (largest < height * (j - i + 1))
                largest = height * (j - i + 1);
        }
        // 분할 정복
        long largestCandidate1 = largest(h, start, midIndex);
        long largestCandidate2 = largest(h, midIndex, end);
        if (largestCandidate1 > largest)
            largest = largestCandidate1;
        if (largestCandidate2 > largest)
            largest = largestCandidate2;
        return largest;
    }
}