[백준 6549 : JAVA] 히스토그램에서 가장 큰 직사각형 / 세그먼트 트리 +분할정복

문제

---

 

 

 

풀이

---

해당 문제는 두 가지 방법으로 풀 수 있다.

1. 스택
2. 세그먼트 트리 + 분할정복

 

해당 풀이는 두 번째 방법이다.

먼저, N=7의 길이를 가지는 수열에 대해 각 세그먼트 트리의 노드에 저장될 구간은 다음과 같다.

 

[그림 1] 세그먼트 트리의 각 노드에 저장될 구간

 

세그먼트 트리는 구간 합에 대한 문제를 통해 처음 배우기 때문에 각 노드에 어떤 값을 저장해야할지 감이 오지 않을 수 있다. (난 그랬다..)

세그먼트 트리에서의 핵심은 구간에 대한 어떤 값을 저장한다는 것이다.

[그림 2] 주어진 히스토그램

 

이제 루트 노드에 1~7번째 구간에 대한 값을 저장해야하는데, 어떤 값을 저장해야할까?

첫 번째로 생각해볼 수 있는 값은 '넓이' 값이다.

[그림 2] 히스토그램 1~7번째 구간에 저장해야할 값

 

최소 높이를 따라야하기 때문에 1~7번째 구간에서의 넓이 값은 (가로: 1 * 7) * (세로: 1) = 7 이다.

그런데, 넓이를 구하기 위해선 최소 높이를 알아야하기 때문에 문제는 다시 원점으로 돌아오게 된다.

 

따라서, 두 번째로 생각해볼 수 있는 값은 '해당 구간에서의 최소 높이' 값이다.

최소 높이만 안다면 넓이는 쉽게 구해지기 때문이다. 하지만, 이 값을 저장하게 되면 최대 넓이를 찾기 위한 분할 정복을 사용할 수 없다. 따라서 최소 높이를 기준으로 좌측과 우측을 분할 정복해가며 최대 넓이를 가지는 사각형을 찾아내기 위해선 해당 구간에서의 최소 높이를 가지는 값의 위치(인덱스) 값이다.

[그림 3] 최소 높이를 기준으로 분할정복을 진행한다.

 

위 그림처럼 최소 높이를 가지는 위치를 기준으로 좌측과 우측에 대해 분할정복을 수행하여 최대 넓이를 찾는다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static final int INF = 1_000_000_000;

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N;
    private static int[] arr;
    private static int[] tree;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            if (N == 0) break;

            arr = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            tree = new int[N * 4];
            init(1, N, 1);

            sb.append(getMaxWidth(1, N)).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    // 세그먼트 트리의 각 노드엔 담당하는 구간의 최솟값을 가지는 인덱스를 저장한다.
    private static int init(int start, int end, int node) {
        if (start == end) return tree[node] = start;

        int mid = (start + end) / 2;
        int leftMinIndex = init(start, mid, node * 2);
        int rightMinIndex = init(mid + 1, end, node * 2 + 1);

        return tree[node] = arr[leftMinIndex] < arr[rightMinIndex] ? leftMinIndex : rightMinIndex;
    }

    // i~j 구간에서 최솟값을 가지는 인덱스를 반환한다.
    private static int query(int start, int end, int node, int i, int j) {
        if (i > end || j < start) return INF;

        if (i <= start && end <= j) return tree[node];

        int mid = (start + end) / 2;
        int leftMinIndex = query(start, mid, node * 2, i, j);
        int rightMinIndex = query(mid + 1, end, node * 2 + 1, i, j);

        if (leftMinIndex == INF) return rightMinIndex;
        else if (rightMinIndex == INF) return leftMinIndex;
        else return arr[leftMinIndex] < arr[rightMinIndex] ? leftMinIndex : rightMinIndex;
    }

    // i~j 구간에서의 최대 넓이를 찾는 메서드.
    private static long getMaxWidth(int i, int j) {
        long maxWidth, tmpWidth;
        int minIndex = query(1, N, 1, i, j);

        // 최소 높이를 바탕으로 넓이 계산.
        maxWidth = (long) (j - i + 1) * (long) arr[minIndex];

        // 왼쪽 존재 ?
        if (i < minIndex) {
            tmpWidth = getMaxWidth(i, minIndex - 1);
            maxWidth = Math.max(maxWidth, tmpWidth);
        }

        // 오른쪽 존재 ?
        if (minIndex < j) {
            tmpWidth = getMaxWidth(minIndex + 1, j);
            maxWidth = Math.max(maxWidth, tmpWidth);
        }

        return maxWidth;
    }
}