[백준] 1725번 : 히스토그램 - 자바(JAVA)

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

1725번: 히스토그램

 

문제 해석

다음과 같은 히스토그램이 주어졌을때 내부의 넓이가 가장 큰 직사각형을 그리려고 합니다.

이때 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하세요

문제 풀이 전 설계

문제에서 직사각형의 넓이가 20억을 넘지 않는다고 하였으므로 int형을 사용해도 될 것 같습니다.

 

히스토그램의 가로 칸의 최대수는 10만이기 때문에 O(NlogN) 시간복잡도로 해결해야 할 것 같습니다.

 

DP를 이용해서 풀이해보고자 했습니다.

 

Math.max( 자기 자신의 높이, 가장 작은 높이 * 연속된 크기, 가장 높은 높이 * 연속된 크기)

 

문제 풀이

이 문제에서 가장 중요한 핵심은 특정 구간에서의 최소높이를 아는것이였습니다.

즉, 위의 그림을 기준으로는 2~3구간의 최소높이가 4이며 이를 통해 넓이가 8임을 알 수 있습니다.

예시를 더 들자면 0~6구간의 최소높이는 1이며 이를 통해 넓이가 7임을 알 수 있습니다.

5~6구간의 최소높이는 3이며 이를 통해 넓이가 6임을 알 수 있습니다.

 

이렇게 구간마다 최소높이를 구해놓은뒤에 분할정복을통해 최대넓이를 구해나갈 수 있습니다.

즉, 세그먼트 트리의 활용문제로 볼 수 있습니다.

 

하지만 풀이는 굉장히 다양합니다

스택을 사용해서 풀이할 수도 있으며, 세그먼트트리를 사용하지 않은 분할정복으로도 해결할 수 있습니다.

 

 

만약 스택을 활용한다면 중요한 핵심은 다음과 같습니다

현재 막대가 이전 막대의 높이보다 작을 경우 현재 막대로 가질 수 있는 최대 높이는 현재 높이이다.

 

문제의 예제에서 스택은 다음과 같이 관리됩니다.

https://st-lab.tistory.com/255

현재 막대의 높이보다 크거나 같은 원소는 모두 삭제하고 그 다음 현재 막대의 index를 넣어주면 됩니다.

넓이는 현재 막대의 높이보다 크거나 같은 원소를 모두 삭제하는 과정에서 구해줍니다.

 

다음 그림을 보면 어떻게 넓이를 구하는지 잘 이해할 수 있을겁니다.

https://st-lab.tistory.com/255

그리고 주의할 점은 순회가 다 끝나면 스택에 잔여 데이터들이 존재할 수 있습니다.

그러므로 나머지 스택에 남겨져 있는 원소들에 대해서도 pop과정을 똑같이 거치면서 넓이를 계산해주면 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main_1725_히스토그램 {

    public static int[] histogram;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        System.out.println(getArea(N));
    }

    public static long getArea(int len) {

        Deque<Integer> stack = new ArrayDeque<Integer>();

        long maxArea = 0;

        for (int i = 0; i < len; i++) {

            /*
             *  이전 체인의 높이보다 현재 히스토그램 높이가 작거나 같을경우
             *  i번째 막대보다 작은 이전 체인들을 pop하면서 최대 넓이를 구해준다.
             */
            while ((!stack.isEmpty()) && histogram[stack.peek()] >= histogram[i]) {
                int height = histogram[stack.pop()];    // 이전 체인의 높이

                /*
                 * pop한 뒤 그 다음의 이전체인이 만약 없다면 0번째 index 부터 (i-1)번째 인덱스까지가
                 * 유일한 폭이 된다. (폭은 i가 됨)
                 * 반면 스택이 비어있지 않다면 이는 pop한 높이보다 더 작은 높이를 갖는
                 * 체인이 들어있다는 것이므로 (i-1)번째 index에서 그 다음 이전 체인의 index를
                 * 빼준 것이 폭이 된다.
                 */
                long width = stack.isEmpty() ? i : i - 1 - stack.peek();

                maxArea = Math.max(maxArea, height * width);    // 최대 넓이 값 갱신
            }

            /*
             *  위 과정이 끝나면 스택에 저장되어있는 체인은 모두 i보다 작거나 같은
             *  체인들 뿐이므로 i번째 index를 넣어준다.
             */
            stack.push(i);

        }

        // 위 과정이 끝나고 Stack에 남아있는 체인들이 존재할 수 있으므로 나머지도 위와같은 과정을 거친다.
        while (!stack.isEmpty()) {
            int height = histogram[stack.pop()];

            /*
             * 만약 pop하고 난 뒤 스택이 비어있다면 이는 남아있는 체인이 없다는 뜻이고
             * 고로 0 ~ (len - 1) 까지인 전체 폭이 width가 되는 것이다.
             */
            long width = stack.isEmpty() ? len : len - 1 - stack.peek();
            maxArea = Math.max(maxArea, width * height);
        }

        return maxArea;

    }


}

 

 

출처

https://st-lab.tistory.com/255

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

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=adamdoha&logNo=222057194023 

1725번 : 히스토그램