[백준] 1725 히스토그램

문제

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

TMI

필자는 지금 스택이라는 알고리즘에 빠져있다.
재밌다. 그냥 재밌다. 막 구현만 하던 나에게 알고리즘이라는 스킬이 더해져 알고리즘푸는 것이 이젠 해당 자료구조 및 알고리즘을 학습하고, 바로 백준의 고난이도 문제까지도 고민 좀 하다보면 풀린다는 것이 재밌습니다.
즉, 어느정도 막구현을 공부했다면, 알고리즘을 배우자.

접근방법

자바의 Stack 클래스를 활용해서 풀었습니다.

code

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 1725 히스토그램 플래티넘 4 Stack 알고리즘으로 풀이.
        // 스택 알고리즘의 종류 중 모노톤 알고리즘이라고 보면됩니다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] histogram = new long[N];
        for (int i = 0; i < N; i++) {
            histogram[i] = Long.parseLong(br.readLine());
        }
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;

        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && histogram[stack.peek()] > histogram[i]) {
                long height = histogram[stack.pop()];
                int width = (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, width * height);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            long height = histogram[stack.pop()];
            int width = (stack.isEmpty() ? N : N - stack.peek() - 1);
            maxArea = Math.max(maxArea, width * height);
        }

        System.out.print(maxArea);
    }
}

코드 설명

1. 히스토그램의 각 바를 loop--> 현재 바의 높이를 확인하고 스택을 이용하려합니다.

2. 스택이 비어있지 않고 스택의 맨 위에 있는 바{ (stack.peek()) --> top라고 인지하면 될 것 같습니다.} 의 높이가 현재 바의 높이보다 클 때까지 스택에서 바를 꺼냄(stack.pop()).
   이를 통해 현재 바를 기준으로 왼쪽에 있는 각 바들의 최대 직사각형 넓이를 구할 수 있게 되는 것입니다.

3. 스택에서 바를 꺼낼 때마다 해당 바의 직사각형 넓이를 계산하고, 최대 직사각형 넓이를 갱신해줍니다 --> 기본적인 스택 원리.
   (이해하기 쉽게 보충 설명을 하면)
   넓이 계산 시 높이는 꺼낸 바의 Height이고, 너비는 i(stack에 남아 있는 바 다음 인덱스 위치)에서 스택의 맨 위에 있는 바 위치를 빼준 너비의 값 (width)입니다.

4. 현재 순회 중인 바를 스택에 데이터(인자) 넣어줍니다(stack.push(i)). 스택에 남아 있는 바들은 계산되지 않은 바들이라서, push 이후 loop에서 계산됩니다.

5. 히스토그램 loop가 완료된 후, 스택에 남아 있는 바들에 대해 직사각형 넓이를 계산해야 합니다. 스택을 전부 비울 때까지 바를 꺼내고(maxArea 업데이트 포함) 해당 바의 직사각형 넓이를 계산하며 최대 직사각형 넓이를 갱신해야 합니다.
   여기서 키 포인트는 --> 넓이 계산 시 높이는 꺼낸 바의 높이(height)이며, 너비는 N(stack에 남아 있는 바 다음 위치)에서 스택의 맨 위에 있는 바 위치를 빼준 값(width)이 되게 된다는 것입니다.