[백준 6549 | 세그먼트 트리] 히스토그램에서 가장 큰 직사각형

 

 

풀이

 

세그먼트 트리를 이용해 O(nlogn) 시간 안에 해결할 수 있는 문제입니다. 모든 세그먼트 트리 문제가 그렇듯, 각 구간에 저장할 정보가 무엇인지를 정하는 것이 문제 해결의 주 요소입니다. 입력받은 숫자들이 담겨 있는 배열의 전체 크기에 함수를 한번 호출하면, 그 함수들의 분할 정복을 통해 최대 직사각형의 넓이를 구하는 방식을 생각해 볼 수 있습니다. 

 

 

예를 들어서 전체 8만큼의 크기를 갖는 배열이 있다고 할 때 (2 1 4 5 1 3 3 1) 전체 구간을 모두 포함하는 직사각형의 넓이와, 최소 높이를 갖는 인덱스를 기준으로 왼쪽 구간을 모두 포함하는 직사각형의 넓이와, 오른쪽 구간을 모두 포함하는 직사각형의 넓이를 비교하여 가장 큰 넓이를 갖는 사각형을 출력하면 되는 것입니다.

 

 

왼쪽 구간을 포함하는 직사각형의 넓이와 오른쪽 구간을 포함하는 직사각형의 넓이는 다시 재귀적으로 해당 구간 전체를 모두 포함하는 직사각형의 넓이와 해당 구간에서 최소 높이를 갖는 인덱스를 기준으로 왼쪽, 오른쪽 구간을 포함하는 직사각형의 넓이를 비교하여 구할 수 있습니다. 따라서 세그먼트 트리에는 해당 구간에서 최소 높이를 갖는 직사각형의 인덱스를 저장하면 됩니다.

 

 

소스 코드(JAVA)

 

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

public class BOJ_6549 {
    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 tok;

        while(true) {
            tok = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(tok.nextToken());
            if (n == 0) break;

            long arr[] = new long[n];
            for(int i=0;i<n;i++) arr[i] = Integer.parseInt(tok.nextToken());
            SegmentTree segTree =  new SegmentTree(n, arr);
            long ans = segTree.findMax(0, n-1);
            bw.write(String.valueOf(ans) + "\n");
        }

        bw.flush();
        bw.close();
    }

    static class SegmentTree {
        int n;
        int[] tree;
        long[] arr;
        SegmentTree(int n, long[] arr) {
            this.n = n;
            this.tree = new int[n*4];
            this.arr = arr;
            this.init(0, n-1, 1);
        }

        public int init(int left, int right, int pos) {
            if(left == right) {
                // store min height index
                return tree[pos] = left;
            }
            int mid = (left + right) / 2;
            int leftMinIndex = init(left, mid, pos * 2);
            int rightMinIndex = init(mid + 1, right, pos * 2 + 1);
            if (arr[leftMinIndex] > arr[rightMinIndex]) return tree[pos] = rightMinIndex;
            return tree[pos] = leftMinIndex;
        }

        public int query(int left, int right, int pos, int posLeft, int posRight) {
            if(left > posRight || right < posLeft) return Integer.MAX_VALUE;
            if(left <= posLeft && posRight <= right) return tree[pos];
            int mid = (posLeft + posRight) / 2;
            int leftMinIdx = query(left, right, pos * 2, posLeft, mid);
            int rightMinIdx = query(left, right, pos * 2 + 1, mid + 1, posRight);

            if (leftMinIdx == Integer.MAX_VALUE) return rightMinIdx;
            else if (rightMinIdx == Integer.MAX_VALUE) return leftMinIdx;
            else if(arr[rightMinIdx] < arr[leftMinIdx]) return rightMinIdx;
            return leftMinIdx;
        }

        public long findMax(int left, int right) {
            int idx = query(left, right, 1, 0, n-1);
            long size = (right - left + 1) * arr[idx];

            if(idx > left) {
                long tempSize = findMax(left, idx - 1);
                size = Math.max(size, tempSize);
            }
            if(idx < right) {
                long tempSize = findMax(idx + 1, right);
                size = Math.max(size, tempSize);
            }
            return size;
        }
    }
}