[알고리즘] 백준 > #1725. 히스토그램

와 진짜 너무 어렵다; 이 문제 뻥 조금 보태서 100번은 본거같은데 매번 너무어렵네~ 얼렁뚱땅 풀기~하고 넘겨버렸는데 오늘은 제대로 풀었다!!!!!!!!! 머리에 쥐날거같았지만 뿌듯하다😇 홀홀..

문제링크

백준 #1725. 히스토그램 (완전.어려움.)

풀이방법

일단 세그먼트트리랑 분할정복으로 풀었다.

세그먼트트리는 구간 내 가장 낮은 높이를 구하기 위함이었고, 분할정복은 가장 낮은 높이를 제외하고 양옆 범위로 진행하며 효과적으로 가장 큰 직사각형을 구하기 위함이었다. 그림으로 큰 흐름을 나타내면 다음과 같다. (여러 조건은 제외한 간단한 흐름이다!)

분할정복의 의미는 "가장 낮은 블럭이 포함되었을 때 가장 넓은 너비를 구했고, 이제 얘를 뺐을 때 가장 넓은 너비들을 구해볼게~" 이다! 이 생각으로 접근하니까 문제가 풀리기 시작했다.

+) 전에 세그먼트트리 문제를 다룰때나 세그먼트트리 관련 글을 작성했을때는 남는부분을 다 채우고 같은 depth의 leaf node들을 두는 포화이진트리를 이용했는데 여기서는 딱 필요한 만큼의 node를 갖는 세그먼트트리를 구성했다. 이게 좀 더 보기도 좋고,, 좋은 방법인거같다! 바보처럼 당연히 이 방식의 세그먼트트리도 완전이진트리라고 생각했는데 절대 아니다 ㅡㅡ 이 잘못된 생각때문에 조금 시간이 걸렸다.. 18개의 leaf node를 가질 때를 그려보면 금방 알 수 있는 실수였다. 관련해서 세그먼트트리 글을 수정하거나 새로 작성할 예정!

코드

import java.util.*;
public class BOJ1725 {

    static int n;
    static Node1725[] tree;
    static int[] heightArr;

    static long maxArea = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        heightArr = new int[n];
        tree = new Node1725[n * 4];

        for (int i = 0; i < n; i++) heightArr[i] = sc.nextInt();

        fillLeaf(1, 0, n - 1);
        searchMaxArea(0, n - 1);

        System.out.print(maxArea);
    }

    private static void searchMaxArea(int sRange, int eRange) {
        long area = getMinHeight(sRange, eRange, 1, 0, n - 1) * (eRange - sRange + 1);
        if (maxArea < area) maxArea = area;

        if (sRange == eRange) return;
        else {
            int minIndex = eRange;
            for (int i = sRange; i < eRange; i++) if (heightArr[minIndex] > heightArr[i]) minIndex = i;

            if (sRange <= (minIndex - 1)) searchMaxArea(sRange, minIndex - 1);
            if ((minIndex + 1) <= eRange) searchMaxArea(minIndex + 1, eRange);
        }
    }

    private static long getMinHeight(int s, int e, int index, int sRange, int eRange) {
        if ((s > eRange) || (e < sRange)) return 1000000001;
        else if ((s <= sRange) && (e >= eRange)) return tree[index].minHeight;

        int mid = (sRange + eRange) / 2;
        return Math.min(getMinHeight(s, e, index * 2, sRange, mid), getMinHeight(s, e, index * 2 + 1, mid + 1, eRange));
    }

    private static int fillLeaf(int index, int sRange, int eRange) {
        if (sRange != eRange) {
            int mid = (sRange + eRange) / 2;
            tree[index] = new Node1725(Math.min(fillLeaf(index * 2, sRange, mid), fillLeaf(index * 2 + 1, mid + 1, eRange)), sRange, eRange);
        } else {
            tree[index] = new Node1725(heightArr[sRange], sRange, eRange);
        }

        return tree[index].minHeight;
    }
}

class Node1725 {

    public int minHeight;
    public int sRange;
    public int eRange;

    public Node1725(int minHeight, int sRange, int eRange) {
        this.minHeight = minHeight;
        this.sRange = sRange;
        this.eRange = eRange;
    }
}