[백준 JAVA] 6549 : 히스토그램에서 가장 큰 직사각형

[백준] 6549 : 히스토그램에서 가장 큰 직사각형 : https://www.acmicpc.net/problem/6549

---

문제 조건 정리

 

1. 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다.
2. 예를 들어, 아래 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
3. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

---

입력

 

1. 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000)
2. 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다.
3. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다.
4. 모든 직사각형의 너비는 1이다.
5. 입력의 마지막 줄에는 0이 하나 주어진다.

---

문제를 풀기 전

 

1. 넓이 저장은 long 타입으로 하자.
2. DP로 풀어야하나? 테이블을 어떻게 구성해야할까?
   
   
3. 결국 알고리즘 분류를 확인하고, 세그먼트 트리에 대해서 공부했다.
   이는 특정 범위 내에서 저장하길 원하는 값을 체계적으로 정리할 수 있었다.
   이번 문제에서는 범위 내의 최소 높이를 갖는 인덱스를 저장했다.
   다른 대표적인 예시로, 범위 내의 합을 저장할 수 있다.
   
   
4. 세그먼트 트리를 구성하기 위해서 히스토그램을 한 칸까지 분할해야겠다.
   한 칸의 높이는 트리의 리프 노드를 구성하게 된다.
   이를 통해 부모를 구성하고, 그 부모를 통해 부모를 구성하는 방식으로 루트까지 초기화해야겠다.

---

코드

 

package baekJoon;

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

public class BJ6549 {

    static long[] heights;
    static int[] segmentTree;

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

            int n = Integer.parseInt(stringTokenizer.nextToken());
            if (n == 0) {
                return; // 종료
            }

            heights = new long[n];

            for (int i = 0; i < n; i++) {
                heights[i] = Long.parseLong(stringTokenizer.nextToken());
            }

            // 세그먼트 트리 초기화
            int h = (int) Math.ceil(Math.log(n) / Math.log(2));  // 트리의 높이 계산
            int size = (int) Math.pow(2, h + 1);  // 전체 노드의 수를 구하여 배열 크기 결정, 루트 노드 인덱스 -> 1
            segmentTree = new int[size];  // 세그먼트 트리 배열 초기화 (4 * n)

            // 범위 -> 0 ~ (n-1)
            // 노드 인덱스 -> 1 (루트)
            initSegmentTree(0, n - 1,1);

            System.out.println(getMaxArea(0, n - 1));
        }

    }

    // 세그먼트 트리 초기화
    private static void initSegmentTree(int start, int end, int nodeIdx) {
        // 더 이상 분할할 수 없는 경우 (리프 노드)
        if (start == end) {
            segmentTree[nodeIdx] = start;  // 리프 노드에는 해당 위치의 인덱스를 저장
            return;
        }

        // 중간 인덱스 계산
        int midIdx = (start + end) / 2;
        // 왼쪽 자식 노드 인덱스
        int leftIdx = 2 * nodeIdx;
        // 오른쪽 자식 노드 인덱스
        int rightIdx = 2 * nodeIdx + 1;

        // 왼쪽 자식 노드 초기화 (start ~ mid)
        initSegmentTree(start, midIdx, leftIdx);

        // 오른쪽 자식 노드 초기화 ((mid + 1) ~ end)
        initSegmentTree(midIdx + 1, end, rightIdx);

        // 왼쪽 자식 노드가 나타내는 범위의 최소 높이 인덱스
        int leftChild = segmentTree[leftIdx];

        // 오른쪽 자식 노드가 나타내는 범위의 최소 높이 인덱스
        int rightChild = segmentTree[rightIdx];

        // 부모 노드는 두 자식 노드 중 더 낮은 높이의 인덱스를 저장
        segmentTree[nodeIdx] = (heights[leftChild] < heights[rightChild]) ? leftChild : rightChild;
    }

    // 재귀적으로 최대 직사각형 넓이 계산
    private static long getMaxArea(int start, int end) {
        // 범위 없음
        if (start > end) {
            return 0;
        }

        // 한 칸
        if (start == end) {
            return heights[start];
        }

        // 전체 범위에서
        // 1번 노드(루트)부터
        // start ~ end 안의
        // 최소 높이 인덱스
        int minHeightIdx = findMinHeightIdx(0, heights.length - 1, 1, start, end);

        // 최소 높이 * 범위
        long maxArea = heights[minHeightIdx] * (end - start + 1);

        // 위 범위의 좌측 최대 넓이
        long leftArea = getMaxArea(start, minHeightIdx - 1);

        // 위 범위의 우측 최대 넓이
        long rightArea = getMaxArea(minHeightIdx + 1, end);

        // 세 범위 중 최대 넓이
        return Math.max(maxArea, Math.max(leftArea, rightArea));
    }

    // 세그먼트 트리에서 현재 노드를 기준으로 주어진 범위 내에서 최소 높이 인덱스 찾기
    // nodeIdx -> 현재 노드 인덱스
    // start ~ end -> 현재 노드가 바라보는 범위 (노드의 범위)
    // left ~ right -> 현재 최소 높이 인덱스를 찾는 범위
    private static int findMinHeightIdx(int start, int end, int nodeIdx, int left, int right) {
        // 현재 노드의 범위와 찾고 있는 범위가 겹치지 않는 경우
        if (left > end || right < start) {
            return -1;
        }

        // 현재 노드의 범위가 찾고 있는 범위에 완전히 포함되는 경우
        if (left <= start && end <= right) {
            return segmentTree[nodeIdx];
        }

        // 현재 노드의 범위가 찾고 있는 범위와 부분적으로 겹치는 경우
        // 세그먼트 트리의 두 자식 노드 중 찾고 있는 범위에 완전히 포함되는 경우를 찾기 위해 재귀 호출
        int mid = (start + end) / 2;
        int leftNode = findMinHeightIdx(start, mid, 2 * nodeIdx, left, right);
        int rightNode = findMinHeightIdx(mid + 1, end, 2 * nodeIdx + 1, left, right);

        // 두 자식 노드 중,
        // 하나가 찾고 있는 범위와 겹치지 않았다면,
        // 하나는 그 범위가 겹친다.
        if (leftNode == -1) {
            return rightNode;
        }

        if (rightNode == -1) {
            return leftNode;
        }

        // 두 자식 노드 모두 찾고 있는 범위와 겹쳤다면,
        // 더 낮은 높이를 갖는 노드의 인덱스를 반환한다.
        return (heights[leftNode] < heights[rightNode]) ? leftNode : rightNode;
    }

}

 

---

문제를 풀고 난 후

 

인덱스를 이리저리 관리하다보니 머리가 뜨끈하다.

 

헷갈리거나 생각이 필요했던 부분에 자세히 주석을 적으며, 결과적으로 세그먼트 트리를 이해한 것 같기는 한데 이런 문제 다시 풀 수 있다고 장담은 못하겠다. 내일 또 풀어야지.

 

코드의 findMinHeightIndex와 같은 메서드를 세그먼트 트리의 컨텍스트에서 query라고 부르던데, 최소값, 최대값, 합계와 같은 값을 검색하는 과정이라고 보여서 그런 듯 하다.

 

맛있었다.