알고리즘 스터디
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형- Python(파이썬)
히치키치
2021. 8. 24. 15:39
문제
https://www.acmicpc.net/problem/6549
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
풀이
- 스택 이용
- 현재 직사각형보다 큰 높이를 pop하여 넓이를 계산
- 나보다 작은 높이가 나올 때까지 넓이를 계산 / 갱신
- 최대 넓이에 대한 계산이 끝나면 현재 직사각형에 대한 넓이를 check 할 수 있도록 push
- N까지 다 돌고 스택에 남은 값에 대해서도 계산

코드
#문제 : https://www.acmicpc.net/status?user_id=omygod0313&problem_id=6549&from_mine=1
import sys
read=sys.stdin.readline
def maxSize():
max_size = 0 #최대 넓이 저장
stack = []
for now in range(N):
left = now #너비 시작점 설정
while stack and stack[-1][0] >= heights[now]:
#새로 추가될 직사각형보다 높이가 높은 경우
h, left = stack.pop()
#pop한 직사각형로 height,left(너비 끝점) 업데이트
tmp_size = h * (now-left) #높이 * (너비 시작점 - 너비 끝점) = 넓이
max_size = max(max_size, tmp_size) #최대 넓이 갱신
stack.append([heights[now],left]) # 스택이 비어있으므로 push
for h, point in stack: # 스택에 남은 직사각형 정보로 max_size 갱신
max_size = max(max_size, (N-point)*h)
return max_size
while True:
N, *heights = map(int,read().split())
if N == 0:
break
print(maxSize())