[백준/트리] 6549번 히스토그램에서 가장 큰 직사각형 (JAVA)

문제

풀이

처음에 접근해서 고민할 때 tree에 뭘 저장해야 하나 모르겠어서 최소 넓이, 최대 넓이같은 걸 생각해봤다. 아무리 생각해도 적절한게 생각이 안 나서 다른 블로그 풀이를 참고했다.. 범위에서의 최소 높이의 인덱스를 저장한다는 것만 블로그에서 힌트로 얻고, 나머지 풀이는 내가 생각해내서 코드를 짜보았다.

설명

• heights[]: 주어진 입력을 Long타입으로 받아 저장한다.
• tree[]: 주어진 구간의 heights 중 최솟값의 인덱스를 저장한다.

initTree()

• 재귀의 종료 조건은 start == end, 즉 리프 노드일 때다.
• tree[node]에 왼쪽과 오른쪽 자식 노드 중 heights에서의 값이 더 작은 놈을 저장한다. 이를 코드로 나타내면 아래와 같다.
  tree[node] = (heights[tree[node * 2]] < heights[tree[node * 2 + 1]] ? tree[node * 2] : tree[node * 2 + 1]);

calcMaxArea()

left와 right 사이에서 만들 수 있는 직사각형의 최대 넓이를 구한다.

1. 현재 범위에서의 최대의 높이를 getMaxHeightIndex()를 통해 구하고 max에 그 때의 넓이를 저장한다.
2. 최대 높이 index를 기준으로, 그 왼쪽과 오른쪽 범위에서 만들 수 있는 최대 넓이를 재귀적으로 구한다.
   • 재귀 호출했을 때,
   • left > right이면 범위가 유효하지 않으므로 0을 반환하고
   • left == right이면 바로 그 높이를 반환한다.
3. 현재 index, 그 왼쪽, 오른쪽 넓이를 비교해서 max를 최댓값으로 갱신한다.

getMaxHeightIndex()

• left와 right 사이에서 만들 수 있는 직사각형의 최대 높이를 구한다.
• start와 end는 node가 포함하는 인덱스의 범위를 의미한다.

left-right와 start-end를 활용해 값을 구해야 하는데, 3가지 경우로 생각할 수 있다.

1. start-end와 left-right가 겹치는 부분이 아예 없는 경우
   → 유효하지 않으므로 INVALID 반환
2. start-end가 left-right에 완전히 포함되는 경우
   → 유효하므로 tree[node] 반환
3. start-end와 left-right가 부분적으로 겹치는 경우
   → 재귀적으로 재탐색

재탐색하는 경우는 아래와 같은 순서로 작동한다.

1. 두 자식 노드에 대해 재귀 호출해서 leftMax와 rightMax를 구한다.
2. 둘 중 하나라도 INAVLID한 경우 나머지 값을 반환한다.
3. 둘다 유효한 값인 경우, heights가 더 작은 노드값을 반환한다.

삽질

별 황당무계한 실수로 1시간정도 삽질을 했다! 억울해! 채점 20퍼에서 계속 오답이 떠서 앞 문제에서 실수했던 부분을 중심으로 다시 살펴보고 로직도 다시 검토했지만 고쳐지지가 않았다.
그러다가 테케로 2 1 10000를 넣으니 답이 10000이 아닌 2가 나왔고, 잘못된 부분을 발견할 수 있었다. 문제는 calcMaxArea()에서 heights[left]가 아닌 heights[tree[left]]를 리턴한 것... 또르륵... 이거 고쳤더니 바로 통과됐다...ㅎㅎ...

코드

import java.io.*;

public class Main {

    private static final String FINISH = "0";
    private static final int INVALID = -1;

    private static int n;
    private static long[] heights;
    private static int[] tree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] line;
        while ((line = br.readLine().split(" ")).length > 1) {
            n = Integer.parseInt(line[0]);
            heights = new long[n + 1];
            tree = new int[(n + 1) * 4];
            for (int i = 1; i <= n; i++) heights[i] = Long.parseLong(line[i]);
            initTree(1, 1, n);
            bw.append(String.valueOf(calcMaxArea(1, n))).append("\n");
        }

        br.close();
        bw.close();
    }

    private static void initTree(int node, int start, int end) {
        if (start == end) {
            tree[node] = start;
            return;
        }
        int mid = (start + end) / 2;
        initTree(node * 2, start, mid);
        initTree(node * 2 + 1, mid + 1, end);
        tree[node] = (heights[tree[node * 2]] < heights[tree[node * 2 + 1]] ? tree[node * 2] : tree[node * 2 + 1]);
    }

    private static long calcMaxArea(int left, int right) {
        if (left > right) return 0;
        if (left == right) return heights[left];
        int index = getMaxHeightIndex(1, 1, n, left, right);
        long max = heights[index] * (long) (right - left + 1);
        max = Math.max(max, calcMaxArea(left, index - 1));
        max = Math.max(max, calcMaxArea(index + 1, right));
        return max;
    }
    
    private static int getMaxHeightIndex(int node, int start, int end, int left, int right) {
        if (start > right || end < left) return INVALID;
        if (start >= left && end <= right) return tree[node];

        int mid = (start + end) / 2;
        int leftMax = getMaxHeightIndex(node * 2, start, mid, left, right);
        int rightMax = getMaxHeightIndex(node * 2 + 1, mid + 1, end, left, right);
        if (leftMax == INVALID) return rightMax;
        if (rightMax == INVALID) return leftMax;
        return (heights[leftMax] < heights[rightMax] ? leftMax : rightMax);
    }
}

참고

[6549번] 히스토그램에서 가장 큰 직사각형