b.1725 히스토그램

 

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

 

 

 

📌 자바(Java)로 푸는 히스토그램에서 가장 큰 직사각형 문제 풀이

🔎 문제 개요

이 문제는 백준 "히스토그램에서 가장 큰 직사각형 (1725번)" 문제입니다.
주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제입니다.

💡 예제 입력

7
2
1
4
5
1
3
3

💡 예제 출력

8

위 입력에 대한 히스토그램을 그려보면 아래와 같습니다.
이때, 가장 큰 직사각형의 넓이는 8입니다.

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 스택(Stack) 을 활용한 O(N) 최적화 방법을 사용합니다.

✏️ 주요 고려 사항

1. 각 히스토그램 막대의 높이(h)를 기준으로 만들 수 있는 가장 큰 직사각형의 넓이를 계산해야 합니다.
2. 스택을 활용하여 효율적으로 넓이를 계산할 수 있습니다.
3. 스택에는 항상 오름차순으로 저장하여, 현재 높이보다 낮아지는 경우 넓이를 계산합니다.
4. 스택이 빌 때까지 남은 높이들에 대한 넓이도 최종적으로 계산합니다.

---

🔹 Java 코드 해설

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

public class b1725 {

    static int N;             // 히스토그램의 막대 개수
    static long answer;       // 가장 큰 직사각형의 넓이
    static Stack<int[]> stack; // 높이와 시작 위치를 저장하는 스택

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); // 막대 개수 입력
        stack = new Stack<>();
        answer = 0;

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine()); // 현재 막대 높이 입력
            int start = i;  // 막대가 시작된 위치

            // 스택의 최상단 값보다 작은 높이가 나오면 넓이 계산
            while (!stack.isEmpty() && stack.peek()[0] > num) {
                int[] top = stack.pop();
                answer = Math.max(answer, (long) top[0] * (i - top[1]));
                start = top[1]; // 시작 위치 업데이트
            }

            stack.push(new int[]{num, start}); // 현재 막대 저장
        }

        // 스택에 남아 있는 높이들에 대한 넓이 계산
        while (!stack.isEmpty()) {
            int[] top = stack.pop();
            answer = Math.max(answer, (long) top[0] * (N - top[1]));
        }

        System.out.println(answer); // 결과 출력
    }
}

---

🔍 코드 설명

📌 1. 스택 활용한 넓이 계산

static Stack<int[]> stack;

• 스택에는 {높이, 시작 위치} 쌍을 저장합니다.
• 오름차순으로 유지되며, 낮아지는 경우 스택을 비우면서 넓이를 계산합니다.

---

📌 2. 현재 높이가 기존 스택보다 낮으면 넓이 계산

while (!stack.isEmpty() && stack.peek()[0] > num) {
    int[] top = stack.pop();
    answer = Math.max(answer, (long) top[0] * (i - top[1]));
    start = top[1]; // 시작 위치 업데이트
}

• 현재 높이가 스택의 최상단보다 낮다면, 넓이를 계산해야 함
• 넓이 계산 공식:

  현재 막대 높이 * (현재 인덱스 - 저장된 시작 인덱스)
  

• 스택의 높이가 낮아질 때까지 pop()하면서 넓이를 갱신

---

📌 3. 스택에 남아 있는 값 처리

while (!stack.isEmpty()) {
    int[] top = stack.pop();
    answer = Math.max(answer, (long) top[0] * (N - top[1]));
}

• 배열의 끝까지 갔을 때, 스택이 비어있지 않다면 최종적으로 남은 값들을 계산해야 합니다.
• 넓이 공식:

  높이 * (전체 길이 - 시작 위치)
  

---

🔥 시간 복잡도 분석

연산 최악의 경우 수행 횟수 시간 복잡도

for 루프	N	O(N)
while 루프 (스택에서 pop)	N	O(N)
while 루프 (마지막 처리)	N	O(N)
총합	O(N)

📌 결론
👉 모든 연산이 O(N) 이내로 수행되므로 효율적입니다.

---

🏆 정리

✅ 핵심 포인트

1. 스택을 활용하여 히스토그램의 넓이를 효율적으로 계산한다.
2. 높이가 낮아지는 순간 스택을 비우면서 직사각형 넓이를 계산한다.
3. 배열의 끝까지 갔을 때, 남은 스택을 한 번 더 체크한다.
4. 시간 복잡도를 O(N)으로 최적화하여 빠르게 해결한다.

🎯 이 알고리즘의 장점

✔ 스택을 활용한 O(N) 풀이로 효율적
✔ 직사각형 넓이를 빠르게 탐색 가능
✔ 다른 "Largest Rectangle" 문제에서도 활용 가능

---

이 글이 도움이 되었다면, 좋아요와 공유 부탁드립니다! 😊