[백준] 6549번 : 히스토그램에서 가장 큰 직사각형- Python(파이썬)

문제

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

6549번: 히스토그램에서 가장 큰 직사각형

 

풀이

• 스택 이용
• 현재 직사각형보다 큰 높이를 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())