[백준/Platinum 5] 1725번 히스토그램 - Java, 자바

1725번 히스토그램

문제

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

문제

요구사항

N개의 막대로 이루어진 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 구해야 한다.

• 직사각형의 밑변은 x축에 평행해야 한다.
• 직사각형은 히스토그램 막대 내부에 완전히 포함되어야 한다.
• N은 최대 100,000개이다.

접근 방식

처음에는 각 막대의 기준으로 좌우를 확장하며 넓이를 구하는 방식만 떠올라 답답하였다. 이렇게 구현하면 효율성이 떨어져 시간초과가 날 것이 뻔하였다. 하지만, 스택을 활용하여 이 문제를 해결할 수 있었다.

모든 계산은 경계를 찾아서 넓이를 구하는 것이 중요하였다. 어떤 막대를 높이로 하는 가장 큰 사각형은, 그 막대 좌우에서 나타나는 첫번째로 높이가 작은 막대에 의해 경계가 결정 되었다.

1. 스택은 항상 높이가 오름차순인 막대들의 인덱스만 갖도록 유지한다.
2. 막대를 하나씩 순회하며, 현재 막대가 스택의 top에 있는 막대보다 높다면 push한다. 하지만, 현재 막대가 스택의 top에 있는 막대보다 높이가 낮으면 낮은 막대가 top에 있던 막대의 '오른쪽 경계'가 된다.
3. 오름차순 규칙이 깨졌다면, pop을 하여 height를 구한다.
   width는 오른쪽 경계 - pop 후 새로운 peek() 인덱스 - 1로 계산한다.
4. 구한 height과 width를 곱하여 넓이를 구해 최대값을 갱신한다.
5. 위와 같은 과정을 반복한다.
6. 위와 같은 과정을 반복 후 스택에 인덱스가 남아있다면, 오른쪽 경계가 없었던 것이다. 그러므로, 오른쪽 경계는 N이 되고 스택이 빌때까지 pop하여 넓이를 구한다.

코드

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

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<n; i++){
            if(stack.isEmpty()){
                stack.push(i);
            }
            else{
                if(arr[stack.peek()] > arr[i]){
                    while (!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                        int height = arr[stack.pop()];
                        int width = 0;
                        if(stack.isEmpty()){
                            width = i;
                        }
                        else{
                            width = i - stack.peek() - 1;
                        }
                        int size = height * width;
                        answer = Math.max(answer, size);
                    }
                    stack.push(i);
                }
                else{
                    stack.push(i);
                }
            }
        }
        while (!stack.isEmpty()){
            int idx = stack.pop();
            int width = n;
            if(!stack.isEmpty()){
                width = n - stack.peek() - 1;
            }

            int height = arr[idx];
            int size = width * height;
            answer = Math.max(answer, size);
        }
        System.out.println(answer);
    }
}

느낀점

이 문제에서 가장 힘들었던 점은 width = i - stack.peek() - 1을 이해하는 것이였다. 이 공식이 외워야하는 암호처럼 느껴졌다. 하지만, "어떤 막대의 최대 넓이는, 그 막대의 높이를 기준으로, 왼쪽과 오른쪽으로 가다가 처음으로 자기보다 낮은 막대를 만나는 지점까지다."라고 생각하였더니 쉽게 접근되고 막대의 경계가 어디인지 완벽히 이해되었다.

수 많은 예외 케이스와 복잡한 너비 계산에 허덕이다 보니, 가장 중요한 원칙을 놓치고 있었다는 것을 깨달았다. 결국 모든 과정은 "어떤 막대의 최대 넓이는 양옆의 낮은 막대에 의해 결정된다."는 단 하나의 원칙을 효율적으로 구현하기 위함이였다. 복잡한 문제에 부딪혔을 때, 한 걸음 물러나 가장 단순한 원칙이 무엇인지 생각하는 것이 중요하다고 느꼈다.