BOJ#6549 히스토그램에서 가장 큰 직사각형

BOJ#6549 히스토그램에서 가장 큰 직사각형

* 문제

https://www.acmicpc.net/problem/6549

* 풀이

세그먼트 트리 + 분할정복으로 풀었습니다.

어려워서 많이 고생한 문제입니다.

- 구하는 것 : 히스토그램에서 가장 큰 직사각형

- 히스토그램은 막대의 집합이고, 모든 막대 x에 대하여 막대 x의 높이로 하면서 만들 수 있는 가장 큰 직사각형들을 구해봅시다.

- 어떤 막대 x에 대하여 양쪽으로 직사각형을 확장해나가면, 막대 x 높이로 만들 수 있는 가장 큰 직사각형을 구할 수 있습니다.

- 우리는 그것들 중 가장 큰 직사각형을 구하면 됩니다.

- 그렇다면 [2 1 4 5 1 3 3]의 히스토그램이 주어졌을 때, 어떤 순서로 막대를 검사하면 될까요

- 가장 작은 막대부터 (높이가 작은 순서대로) 검사하는게 좋습니다.

- [2 1 4 5 1 3 3]에서 1번 막대의 높이로 만들 수 있는 가장 큰 직사각형의 넓이는 7이 될 것입니다.

- 1번 막대의 검사가 끝났고, 1번 막대는 배제할 수 있습니다.

- 자연스럽게 두 구간으로 분할됩니다 [2], [4 5 1 3 3]

- 위 과정 반복.

- 시간복잡도를 생각해보면, N개의 모든 막대에 대해 위 과정을 진행하고(O(N)), 각 과정에서 가장 짧은 막대를 구해야 하기 때문에 총 시간 복잡도는 O(N^2)이 될 것입니다.

- 여기서 가장 짧은 막대를 구할때 세그먼트 트리를 사용하면 구간의 최소값을 query하는데 O(logN)으로 줄일 수 있습니다.

- 따라서, 시간 복잡도는 O(N^2) -> O(N logN)이 됩니다.

- 세그먼트 트리를 처음 접해보시는 분들은 세그먼트 트리 기초 문제를 풀고 오시는 것을 추천드립니다.

* 테스트 케이스

http://www.informatik.uni-ulm.de/acm/Locals/2003/input/histogram.in

http://www.informatik.uni-ulm.de/acm/Locals/2003/output/histogram.out

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%236549/src/Main.java

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {

            // Input
            String input = br.readLine();

            if (input.equals("0")) return;

            StringTokenizer st = new StringTokenizer(input);

            int N = Integer.parseInt(st.nextToken());

            int[] histogram = new int[N];
            for (int i = 0; i < N; i++) histogram[i] = Integer.parseInt(st.nextToken());

            // Solve
            SegmentTree segmentTree = new SegmentTree(histogram, N);

            System.out.println(queryMaxArea(histogram, segmentTree, N, 0, N - 1));

        } // ~test case loop
    } // ~main

    static long queryMaxArea(int[] histogram, SegmentTree segmentTree, int N, int left, int right) {

        if (left == right) return histogram[left];

        int minIdx = segmentTree.query(histogram, left, right, 1, 0, N - 1);

        long maxArea = (long) histogram[minIdx] * (right - left + 1);

        if (minIdx - 1 >= left) {

            long leftTempMax = queryMaxArea(histogram, segmentTree, N, left, minIdx - 1);
            maxArea = maxArea < leftTempMax ? leftTempMax : maxArea;
        }

        if (minIdx + 1 <= right) {

            long rightTempMax = queryMaxArea(histogram, segmentTree, N, minIdx + 1, right);
            maxArea = maxArea < rightTempMax ? rightTempMax : maxArea;
        }

        return maxArea;
    }
}

class SegmentTree {

    int[] segmentArr; // The array that stores segment tree nodes

    SegmentTree(int[] arr, int n) {

        int x = (int) Math.ceil(Math.log(100000) / Math.log(2));

        int segmentSize = (int) Math.pow(2, x) * 2;

        segmentArr = new int[segmentSize];

        init(arr, 0, n - 1, 1);
    }

    int init(int[] arr, int left, int right, int node) {

        if (left == right) return segmentArr[node] = left;

        int mid = (left + right) / 2;

        int leftChildNode = init(arr, left, mid, node * 2);
        int rightChildNode = init(arr, mid + 1, right, node * 2 + 1);

        return segmentArr[node] = arr[leftChildNode] <= arr[rightChildNode] ? leftChildNode : rightChildNode;
    }

    int query(int[] arr, int left, int right, int node, int nodeLeft, int nodeRight) {

        // 두 구간이 겹치지 않는 경우
        if (right < nodeLeft || left > nodeRight) return -1;

        // 노드 구간이 완전히 속하는 경우
        if (left <= nodeLeft && right >= nodeRight) return segmentArr[node];

        int nodeMid = (nodeLeft + nodeRight) / 2;

        int leftChildNode = query(arr, left, right, node * 2, nodeLeft, nodeMid);
        int rightChildNode = query(arr, left, right, node * 2 + 1, nodeMid + 1, nodeRight);

        if (leftChildNode == -1) return rightChildNode;
        else if (rightChildNode == -1) return leftChildNode;
        else return arr[leftChildNode] <= arr[rightChildNode] ? leftChildNode : rightChildNode;
    }
}