[BOJ/백준] 6549 - 히스토그램에서 가장 큰 직사각형 (Python)

문제

문제링크

너비가 1인 직사각형으로 이루어진 히스토그램이 있다.

각 줄에서 첫 번 째 값은 직사각형의 수이고, 그 후 값들은 히스토그램의 높이다.

히스토그램에서 가장 널이가 큰 직사각형을 구하라.

 

풀이

stack에는 높이와 시작 인덱스를 저장한다.

스택에 값이 있고 마지막 값의 높이가 현재 높이보다 크다면, 높이와 시작 인덱스를 꺼내 현재 위치 i에서의 크기를 구한다.

최대 크기와 이 크기 중 큰 값을 max_s에 재저장한다.

스택에는 현재 높이와시작 인덱스를 저장한다.

스택에 남은 직사각형을 처리하기 위해 for문을 다시 써주고, max_s를 리턴한다.

이 과정을 입력이 0이기 전까지 반복한다. 

 

코드

import sys
input=sys.stdin.readline

def maxsize():   #최대 크기의 직사각형 구하는 함수
    max_s=0   #최대 크기 
    stack=[]   #높이, 시작 인덱스 저장

    for i in range(n):
        idx=i   #현재 인덱스
        while stack and stack[-1][0]>=hs[i]:
            h, idx=stack.pop()
            size=h*(i-idx)   #현재 높이 h인 직사각형의 크기
            max_s=max(max_s, size)   #최대 크기 갱신
        stack.append([hs[i], idx])   #현재 높이와 시작인덱스 추가
    for h, left in stack:   #스택에 남아있는 직사각형 처리
        max_s=max(max_s, (n-left)*h)
    return max_s

result=[]
while True:
    n, *hs=map(int, input().split())
    if n==0:
        break
    result.append(maxsize())

print(*result, sep='\n')