[Java] 백준 1725번 - 히스토그램

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

 

----------------------------------------------------------------------------------------------------------------------

[문제 풀이]

각각의 칸을 기준으로 양옆으로 확장하여 최대 직사각형을 구한후, max값을 계속 갱신시켜주는 방법 풀이하였습니다.

예를 들어, 0번~6번의 블록이 주어졌을때,  index번째 기준블록의 높이를 height, 왼쪽으로 최대한 확장한 index를 start, 오른쪽으로 최대 확장한 index를 end라고 한다면, 넓이식은 ((end-start)+1)*height가 됩니다.

1번 블록 기준을 살펴보면 왼쪽으론 0번까지, 오른쪽으론 6번까지 확장이 가능합니다.

따라서 1번 블록기준 최대 넓이는 ((6-0) + 1 )* 1 = 7

2번 블록 기준으로 살펴보면 왼쪽으로 2번까지, 오른쪽으론 3번까지 확장이 가능합니다.

따라서 2번 블록기준 최대 넓이는 ((3-2) + 1 )* 4 = 8

 

[정답 코드]

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

public class Main {
    public static int N;
    public static int[] histogram;
    public static int max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        histogram = new int[N];

        for(int i=0;i<N;i++) {
            histogram[i] = Integer.parseInt(br.readLine());
        }

        for(int i=0;i<N;i++) {
            int area = findArea(i);
            if(max < area) {
                max = area;
            }
        }
        System.out.println(max);
    }
    public static int findArea(int index) {
        int height = histogram[index];
        // index 왼쪽으로 확장할 수 있는 최대 길이 구함
        int start = index;
        while(start > 0) {
            start--;
            if(histogram[start] < height) {
                start++;
                break;
            }
        }

        // index 오른쪽으로 확장할 수 있는 최대 길이 구함
        int end = index;
        while(end < N - 1) {
            end++;
            if(histogram[end] < height) {
                end--;
                break;
            }
        }
        return (end - start + 1) * height;
    }
}