이번에 풀어본 문제는
백준 6549번 히스토그램에서 가장 큰 직사각형 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int [] map;
    static int [] tree;
    static int N;
    static long answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while(true)
        {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            if(N == 0) break;
            map = new int[N + 1];

            for(int i = 1; i <= N; ++i) map[i] = Integer.parseInt(st.nextToken());

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

            answer = Long.MIN_VALUE;
            getMaxArea(1,N);

            sb.append(answer).append("\n");
        }
        System.out.print(sb);
    }
    static int setTree(int start, int end, int node)
    {
        if(start == end) return tree[node] = start; // 리프노드

        int mid = (start + end) / 2;
        int left = setTree(start,mid,node * 2);
        int right = setTree(mid + 1,end,(node * 2) + 1);

        return tree[node] = map[left] < map[right] ? left : right;
    }

    static int getMinIdx(int start,int end,int left, int right,int node)
    {
        if((left > end) || (right < start)) return -1;
        else if((start >= left) && (end <= right)) return tree[node];

        int mid = (start + end) / 2;
        int leftMin = getMinIdx(start,mid,left,right,node * 2);
        int rightMin = getMinIdx(mid+1,end,left,right,(node * 2) + 1);

        if(leftMin < 0) return rightMin;
        else if(rightMin < 0) return leftMin;
        return map[leftMin] < map[rightMin] ? leftMin : rightMin;
    }

    static void getMaxArea(int start, int end)
    {
        if(start > end) return;
        int idx = getMinIdx(1,N,start,end,1);
        answer = Math.max(answer,(long)map[idx] * ((end - start) + 1));

        getMaxArea(start,idx-1);
        getMaxArea(idx+1,end);
    }
}

📝 풀이

N개의 각각의 높이를 가진 히스토그램이 입력으로 주어질 때, 히스토그램의 범위 내에서 만들 수 있는 가장 큰 직사각형의 넓이를 출력하는 문제입니다.
세그먼트 트리를 활용했고, 트리의 각 노드는 해당 범위 내의 가장 낮은 높이를 가진 인덱스를 가집니다.
그 이유를 파악하기 위해 getMaxArea 함수를 보면,
해당 함수는 먼저 getMinIdx함수를 통해 현재 범위내에서 가장 작은 높이의 인덱스를 받아옵니다. 구하고자 하는 히스토그램의 범위가 트리 초기화 단계에서 만들었던 범위와 항상 일치하지 않기 때문에 getMinIdx함수를 구현해 주어야 합니다. 가장 낮은 높이의 인덱스를 구했다면, 우선 해당 높이를 포함한 넓이를 구해줍니다(가로 = start~end범위 / 세로 = 인덱스의 높이). answer 값을 최댓값으로 갱신해 준 후 아래쪽으로 따라가 보면, 받아온 최소 인덱스를 기준으로 좌측과 우측범위로 분할정복을 합니다.
왜냐하면, 어떤 한 범위 내에서 직사각형의 넓이를 구할 때, 가장 큰 제약조건이 높이의 차이이기 때문에, 해당 범위의 최소 인덱스의 높이를 기준으로 구할 수 있는 최댓값을 구해놓고, 사용한 인덱스를 제외한 좌/우측 범위의 히스토그램을 분할정복하며 최댓값을 갱신해 줄 수 있습니다.

📜 후기

세그먼트 트리는 기본 문제만 풀어봐서 그런지 굉장히 어려운 문제였어요..
다른 블로그들을 보시면 그림과 함께 설명된 아주 좋은 글들이 많아요! 참고하시면 도움 될것같습니다 ^^