[백준] 6549번 - 히스토그램에서 가장 큰 직사각형

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

1. 문제 접근 - 처음 생각했던 방식들

히스토그램에서 가장 큰 직사각형을 구하는 문제.

처음에는 자연스럽게 브루트포스로 접근했다.

 1) 시도 1

각 막대를 기준으로
좌우로 확장하면서 “자기보다 크거나 같은 구간 길이”를 구함

• 시간복잡도: O(n³) 수준
• 바로 시간초과 예상

---

 2) 시도 2

높이 기준으로 접근
(예: 높이 1 ~ max 높이까지 각각 구간 계산)

• 시간복잡도: O(n × h)
• h 최대가 10억이라 불가능

---

→ 여기서 깨달은 점:

“이 문제는 구간을 찾는 문제가 아니라
각 막대가 ‘최소 높이’가 되는 최대 구간을 찾는 문제다.”

---

2. 핵심 아이디어

어떤 막대 하나를 기준으로 보면

• 높이 = 그 막대 높이
• 너비 = 그 막대보다 낮은 막대를 만날 때까지 확장한 길이

즉,

“이 막대가 최소 높이일 때 만들 수 있는 최대 직사각형”

을 계산하면 된다.

---

3. 해결 전략 - 스택

핵심 포인트

• 스택에는 인덱스를 넣는다
• 스택은 항상 높이가 증가하는 구조 유지

---

4. 가장 중요한 순간

→ 현재 높이가 더 작아지는 순간

현재 높이 < 스택 top 높이

 

이 순간:

“스택 top 막대의 오른쪽 확장이 끝난 것”

→ 즉, 넓이를 계산해야 하는 타이밍

---

5. 넓이 계산 방식

막대를 하나 pop 했다고 하면

높이

h = rects[top]

너비

if stack:
	width = i - stack[-1] - 1
else:
	width = i

---

6. 왜 이렇게 계산되나?

• 현재 i는 처음으로 나보다 작은 막대 위치
• 그래서 오른쪽 끝은 i - 1

왼쪽은

• pop 후 stack[-1]이 나보다 작은 첫 위치

그래서

width = (오른쪽 - 왼쪽 + 1) # 오른쪽은 현재 입력, 왼쪽은 아래 상황에 따라 다름
1) 왼쪽 = (i - 1) - (stack[-1] + 1) + 1 # 스택에 요소가 있는 경우
2) 왼쪽 = i - stack[-1] - 1 # 스택이 비어있는 경우

---

7. 내가 했던 실수

 1) 인덱스를 높이처럼 사용

height = stack.pop() #  잘못된 사용

 

→ 실제 높이는 height = rects[idx]

 

---

 2) 너비를 단순히 개수로 계산

for width, height in enumerate(locale):
	M = max(M, height * (width + 1))

→ 문제점

• pop된 개수 ≠ 실제 너비
• 왼쪽 경계 고려 안됨

---

 3) pop을 모아서 처리

locale.append(stack.pop())

 

→ 문제점

• 넓이는 pop하는 순간 계산해야 함
• 나중에 모아서 계산하면 경계 정보가 사라짐

---

8. 최종 코드

import sys
input = sys.stdin.readline

while True:
    data = list(map(int, input().split()))
    if data[0] == 0:
        break
    n = data[0]
    rects = data[1:] + [0]
    stack = []
    M = 0

    for i in range(n + 1):
        while stack and rects[stack[-1]] > rects[i]:
            h = rects[stack.pop()]

            if stack:
                width = i - stack[-1] - 1
            else:
                width = i
            M = max(M, h * width)
        stack.append(i)
    print(M)