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

문제 해석

• 0을 입력받을 때까지 막대기 수(N)을 입력 받고 같은 줄에 막대기 높이를 입력받는다.
• 모두 입력 받았다면 막대기의 가로(너비)가 1인 막대기를 조합하여 가장 넓이가 큰 직사각형의 너비를 구하면 된다.
  
  

코드

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

public class Main {

    static int[] histogram;

    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();

        int N;

        while(true){
            st = new StringTokenizer(br.readLine(), " ");

            N = Integer.parseInt(st.nextToken());

            if(N == 0){ //종료 조건
                break;
            }

            histogram = new int[N];

            for(int i = 0; i < N; i++){ //히스토그램 입력
                histogram[i] = Integer.parseInt(st.nextToken());
            }

            sb.append(dividArea(0, N-1)).append("\n");

        }

        br.close();
        System.out.println(sb);

    }

    //히스토그램 분할
    static long dividArea(int start, int end){
        
        if(start == end) { //더 이상 분할 할 수 없을 때
            return histogram[end];
        }

        int middle = (start+end)/2;

        //(0 ≤ hi ≤ 1,000,000,000) 이기 때문에 long형
        long leftHeight = dividArea(start, middle);
        long rightHeight = dividArea(middle+1, end);

        long maxWidth = Math.max(leftHeight, rightHeight); //쪼개는 순으로 최대값을 가져옴.

        /*
        * 쪼개지는 부분에 서로 이웃한 부분이 최대가 될 수 있기 때문에
        * 중간 분위 탐색해서 최대값을 한번 더 비교해 구한다.
        * */

        maxWidth = Math.max(maxWidth, getWidthToMiddle(start, end, middle));

        return maxWidth;
    }


    static long getWidthToMiddle(int start, int end, int middle){
        int toLeft = middle;  //중간 지점부터 왼쪽으로
        int toRight = middle; //중간 지점부터 오른쪽으로

        //중간 지점 높이
        long midHeight = histogram[middle];

        // 초기 넓이
        long maxArea = midHeight;

        while(start < toLeft && toRight < end) { //서로 중간부터 벌어지면서 끝 범위를 벗어나기 전까지만 반복

            //midHight에 작은 값을 넣는 이유 : 직사각형 넓이는 작은 높이가 높이 값이 됨.
            if(histogram[toLeft - 1] < histogram[toRight + 1]) { //중간 지점을 기준으로 벌어지는데 오른쪽의 값이 더 클경우
                toRight++;
                midHeight = Math.min(midHeight, histogram[toRight]);
            }
            else { //중간 지점을 기준으로 벌어지는데 왼쪽 값이 더 클 경우
                toLeft--;
                midHeight = Math.min(midHeight, histogram[toLeft]);
            }

            // 최대 넓이 갱신 (움직인 만큼의 각 막대기의 움직인 거리만큼 * 높이)
            maxArea = Math.max(maxArea, midHeight * (toRight - toLeft + 1));
        }

        // 오른쪽 부분을 끝까지 탐색 못했다면 마저 탐색
        while(toRight < end) {
            toRight++;
            midHeight = Math.min(midHeight, histogram[toRight]);
            maxArea = Math.max(maxArea, midHeight * (toRight - toLeft + 1));
        }

        // 왼쪽 부분을 끝까지 탐색 못했다면 마저 탐색
        while(start < toLeft) {
            toLeft--;
            midHeight = Math.min(midHeight, histogram[toLeft]);
            maxArea = Math.max(maxArea, midHeight * (toRight - toLeft + 1));
        }

        return maxArea;
    }
}

결과

느낀 점

정렬 문제를 풀때와 유사한 느낌을 받았는데 그래도 꽤나 생각을 좀 많이 해야하는 문제였던 것 같다... 처음에 단순하게 '막대기 수가 많이 들어가고 높이가 가장 큰을 둘다 최선일 수 있는 해를 찾으면 되겠다' 라고 생각해서는 절대 풀 수 없는 문제이지 않나 싶다,,, 예전엔 순차대로 이웃한걸 탐색하는 알고리즘을 풀었다면 이 문제는 기준점을 여러개 잡는다는 점에서 난이도가 있게 느껴졌다... (아직 부족해서 그런거겠지만 ㅎ....)