[BOJ1725] 히스토그램

문제 설명

문제 링크

• 너무나 유명한, 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제이다.
• 예전에 세그먼트 트리를 이용하여 풀었었다. (이전 포스팅 참고)
• 이번에는 조금 더 효율적인 스택 방식을 이용하여 O(n), 즉 한번의 순회로 해결하는 방법에 대해 소개하려 한다.

풀이 과정

• 규칙은 간단하다. 0번 막대기부터 순서대로 스택에 쌓아 나가되, 현재 내가 보는 막대기와 스택의 top에 있는 막대기 크기를 비교하여, 스택의 top에 있는 막대기의 크기가 크다면 pop을 하고 쌓고, 아니면 현재 막대기를 push 한다. (즉 막대의 높이가 증가하는 방향으로만 스택이 쌓인다.)
• pop을 한다고 하면 조금 막연한데, 현재 보는 막대기와 스택의 top에 있는 막대기를 비교해서 스택의 top에 있는 막대기가 더 크다는 것은, 스택에 있는 막대기가 높이가 되는 직사각형은 현재 내가보고 있는 인덱스 전까지 밖에 가로의 길이가 설정되지 못한다는 것이다.
• 그래서 pop을 하며, top에 있던 막대기를 높이로 하는 최대 직사각형의 넓이를 구하는 것이다.
• 가로의 길이는 현재 내가보고 있는 막대기 전, 그리고 스택에 top(한번 pop 한 상황)에 있는 막대기의 인덱스 후가 된다.
• 즉 높이는 스택의 top에 있던 막대기의 길이, 가로는 현재 인덱스 - 스택의 다음 top의 인덱스 - 1이 된다.
• 만약 가로의 길이를 구하는 과정에서, 왼쪽 점을 구하려하는데 stack이 비어있다면 그건 무슨 뜻일까?
• 그 히스토그램 막대기보다 작은 막대기가 왼쪽에는 없다는 말이 된다. 그러므로, 0부터 가로의 길이를 설정하면 된다.
• 이러한 과정이 끝나고 나면, 여전히 스택에서 빠져나오지 못한 막대기들이 크기 순으로 들어있다.
• 남아있는 막대기에 대해서도 똑같이 진행하면, 결국 최대 직사각형 넓이를 쉽게 구할 수 있게 된다.
• 다소 설명이 어렵지만, 천천히 코드와 함께 보면 금방 이해할 수 있을 것이다.

코드

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

public class BOJ1725_히스토그램_스택 {
    static int output;
    static int[] histo;
    static Deque<Integer> stack = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        histo = new int[N+1];
        histo[0] = 0;
        for (int i=1; i<=N; i++){ 
            // 히스토그램 입력
            histo[i] = Integer.parseInt(br.readLine());
        }
        for (int i=1; i<=N; i++){
            // 스택이 비어있지 않거나, 현재 막대보다 스택 막대가 더 크다면
            while (!stack.isEmpty() && histo[stack.peek()] > histo[i]){
                int height = histo[stack.poll()];
                int width = stack.isEmpty()? i - 1 : i - stack.peek() - 1;
                output = Math.max(output, height * width);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            // 남은 스택에 대해 진행
            int height = histo[stack.poll()];
            int width = stack.isEmpty() ? N : N - stack.peek() - 1;
            output = Math.max(output, height * width);
        }
        System.out.println(output);
    }
}