골드에그

1. 문제요약

6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net)

히스토그램이 주어질 때, 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

2. 문제예제

( ※ 본 문제는 팩트추출하기 전에 문제풀이(수동)을 먼저 작성한다. )

3. 문제풀이(수동)

위와 같이 히스토그램 예제가 있을 때, 0번부터 7번까지 순차적으로 문제푸는 방식과 문제를 분할하여 푸는 방식 2가지가 존재한다. 세그먼트 트리를 이용하는 방법도 있다고는 하는데 여기서는 생략한다.

1) 스택활용

먼저 순차적으로 문제푸는 방식으로 예제를 풀어보면, 다음과 같다.

H[0] * 1 = 3 ===> MaxArea 3 으로 갱신

H[4] * (5-4) = 5 * 1 = 5 ===> MaxArea 5 로 갱신

H[3] * (5-3) = 4 * 2 = 8 ===> MaxArea 8 로 갱신

H[2] * (5-2) = 3 * 3 = 9 ===> MaxArea 9 로 갱신

H[1] * 5 = 2 * 5 = 10 ===> MaxArea 10 으로 갱신

H[7] * (7-6) = 3 * 1 = 3

H[6] * (7-5) = 3 * 2 = 6

H[5] * 8 = 1 * 8 = 8

따라서 정답은 10 이다.

2) 분할정복

다음은 문제를 분할정복해서 나누어 풀 때 방식이다. 다음과 같다.

일단 문제를 mid 중심으로 나누어 쪼갠다. 좌측과 우측에서 가장 세로 길이가 큰 직사각형을 구하고, 중간 부분부터 가로의 길이를 확장해 나가면서 가로의 길이가 큰 직사각형을 구한다. 세로 길이가 큰 직사각형의 넓이를 구하는 함수를 getArea 라고 하고 중간 영역부터 확장해서 직사각형의 넓이를 구하는 함수를 getMidArea 라고 할 때 수동 풀이는 다음과 같다.

• getArea(0, 7)
  • getArea(0, 3)
    • getArea(0, 1)
    • getMidAread(0, 1, 0)
    • maxArea : 4
    •  
    • getArea(2, 3)
    • getMidAread(2, 3, 2)
    • maxArea : 6
  • getMidArea(0, 3, 1)
  • maxArea : 8
•  
  • getArea(4, 7)
    
    • getArea(4, 5)
    • getMidAread(4, 5, 4)
    • maxArea : 5
    •  
    • getArea(6, 7)
    • getMidAread(6, 7, 6)
    • maxArea : 6
  • getMidArea(4, 7, 5)
  • maxArea : 6
• getMidArea(0, 7, 3)
• maxArea : 10

이 풀이방식의 정답도 10 이다.

문제를 절반으로 나누어서 재귀 호출하고, 각각 O(N) 시간만큼 소요되니 O(NlgN) 시간 복잡도를 가진다. getMidArea 부분을 살펴보면 N 크기의 배열을 나누어서 문제를 푸는데 getMidArea(0,7,3) 처럼 최악의 케이스가 N 복잡도를 가지기 때문이다.

4. 팩트추출

Fact 1 : 스택 활용편의 예제를 살펴보면, "직사각형의 가로 넓이를 확장해 나가는 방향은 자신의 높이보다 작으면서 양 옆에 있는 높이 중 큰 높이를 골라야 한다." 는 점을 알 수 있다. 이 논리와 더불어 순차적으로 문제를 풀기 때문에 (0 => N) 자신의 크기보다 작은 높이가 나왔을 때 비로소 자신과 그 이전 크기들을 한 꺼번에 계산한다. 계산하는 방식을 보면 데이터를 쌓아두었다가 마지막부터 계산하므로 스택 구조를 사용해야 하는 것을 알 수 있다.

Fact 2 : 문제를 좌측에서 가장 큰 사각형과 우측에서 가장 큰 사각형, 중간에서 가장 큰 사각형을 구하는 문제로 분할할 수 있다. 분할 문제이긴 하지만 이전에 계산한 답안을 재사용하진 않는다. 따라서 DP 문제로 풀 수는 없고 분할정복으로만 풀 수 있다.

Fact 3 : 문제를 중심으로 분할해서 재귀로 풀 경우, 좌측에서 가장 큰 사각형을 구하는 부분과 우측에서 가장 큰 사각형을 구하는 부분은 막대의 넓이가 1 일때 세로 길이가 가장 큰 사각형이다. 결국 중간에서 가장 큰 사각형을 구하는 함수 부분이 핵심이다.

5. 문제전략

문제 전략은 예제 풀이(수동)과 팩트 추출을 통해 알아보았다. 스택을 활용하는 방식과 분할 정복으로 문제를 풀 수 있다.

6. 소스코드

1) 스택활용

private static long getArea(int len) {
    Stack<Integer> stack = new Stack<>();
    long max=0;

    for (int i=0; i<N; i++) {
        while (!stack.isEmpty() && histogram[stack.peek()] > histogram[i]) {
            int index = stack.pop();
            int width = stack.isEmpty() ? i : i-stack.peek()-1;
            max = Math.max(max, (long)width*histogram[index]);
        }
        stack.push(i);
    }

    while(!stack.isEmpty()) {
        int index = stack.pop();
        int width = stack.isEmpty() ? N : N-stack.peek()-1;
        max = Math.max(max, (long)width*histogram[index]);
    }
    return max;
}

2) 분할정복

private static int getArea(int left, int right) {
    if (left == right) return histogram[left];
    int mid = (left + right) / 2;
    int max = Math.max(getArea(left, mid), getArea(mid+1, right));
    max = Math.max(max, getMidArea(left, right, mid));
    return max;

}
private static int getMidArea(int left, int right, int mid) {
    int leftPointer = mid;
    int rightPointer = mid+1;
    int height = Math.min(histogram[leftPointer], histogram[rightPointer]);
    int result = height*2;

    while (left<leftPointer || rightPointer<right) {
        if(rightPointer < right && (leftPointer == left || histogram[leftPointer-1] < histogram[rightPointer+1])) {
            ++rightPointer;
            height = Math.min(height, histogram[rightPointer]);
        } else {
            --leftPointer;
            height = Math.min(height, histogram[leftPointer]);
        }
        result = Math.max(result, height * (rightPointer - leftPointer +1));
    }
    return result;
}