[BOJ/Java] 6549. 히스토그램에서 가장 큰 직사각형

[BOJ/Java] 6549. 히스토그램에서 가장 큰 직사각형

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

---

🔍 문제 분석

백준 6549번 "히스토그램에서 가장 큰 직사각형" 문제는 주어진 히스토그램에서 가장 넓은 직사각형을 찾는 문제이다.
주어진 히스토그램은 N개의 막대기로 이루어져 있으며, 각 막대기는 서로 너비가 1이고 높이가 주어진다.

---

🚀 풀이 과정

이 문제는 스택을 이용한 최적화된 방법을 사용해야 한다.

💡 핵심 아이디어

• 각 막대의 높이를 기준으로 최대 직사각형을 계산해야 한다.
• 스택을 활용하면 O(N) 시간에 해결할 수 있다.

1. 스택을 활용한 접근 방법

1. 막대를 왼쪽부터 확인하면서 스택에 저장한다.
   • 스택에는 막대의 인덱스를 저장한다.
   • 현재 막대의 높이가 스택의 top보다 작다면, 스택에서 pop하면서 직사각형을 계산한다.
2. 스택에서 pop할 때 최대 직사각형을 계산한다.
   • pop된 막대의 높이를 h라고 하면,
   • 너비는 i - 스택의 top - 1로 계산할 수 있다.
3. 모든 막대를 스택에 넣고, 마지막에 스택이 빌 때까지 최대 직사각형을 갱신한다.

---

💻 코드 구현

아래는 Java로 구현한 코드이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            if (n == 0) break; // 입력 종료
            
            int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
                heights[i] = Integer.parseInt(st.nextToken());
            }

            sb.append(getMaxRectangle(heights)).append("\n");
        }

        System.out.print(sb);
    }

    public static long getMaxRectangle(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];

            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                maxArea = Math.max(maxArea, (long) height * width);
            }

            stack.push(i);
        }

        return maxArea;
    }
}

---

⏳ 시간 복잡도 분석

• 스택에 모든 원소를 한 번씩 push & pop
• 각 원소는 최대 1번 push, 1번 pop
• 따라서 O(N) 의 시간 복잡도를 가진다.

---

🤔 느낀점

• 스택을 활용하여 최적화할 수 있는 패턴을 익혔다.
• 단순히 모든 직사각형을 계산하면 O(N²)로 비효율적이지만,
  스택을 활용하면 O(N)으로 해결 가능하다.
• 마지막에 인덱스 n까지 확장하여 처리하는 테크닉을 배웠다.

이 문제를 통해 스택을 활용한 최적화 패턴을 확실히 익힐 수 있었다! 🚀