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

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

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

<문제 해설>

stack 문제이다. 지금까지 추가된 상자가 언제부터 이어져왓는지 기록해야한다.

만약 추가되는 상자가 이전 상자보다 작다면 현재 상자와 이전 큰 상자의 차이는 필요가 없어짐으로 이전 상자가 얼마나 큰지 계산해서 가장 큰 상자인지 max로 비교해 검증해준다. 현재 상자는 큰 상자와 같이 이어짐으로 현재상자가 큰 상자가 추가됐을때 추가된것처럼 기록한다. 현재 상자를 stack에 넣어준다.

만약 추가되는 상자가 이전 상자보다 크다면 그냥 stack에 추가해준다.

모든 상자를 검증한 후에는 stack에 남아 있는 값을 처리하는데 stack에 사라지지 않고 남아있다는 뜻은 끝까지 남아있었다는 거니 (N - 상자가 시작한 시점) * 상자의 키를 곱해서 최대값인지 비교해준다.

<예시>

왼쪽에서 오른쪽으로 상자가 들어오는 그림이다.

왼쪽을 보면 상자가 4가 있었고 5가 추가되는 모습인데 현재 추가되는 상자가 더 크니

stack = [[4,0],[5,1]]

스텍이 다음과 같이 된다.

오른쪽을 보면 4가 추가될때 5보다 작으니까 stack을 빼서 최대값이랑 계산하게 되고 4의 시작지점을 5의 시작지점으로 바꿔준다.

stack = [[4,0]]

<코드>

import sys

while(1):
    numbers = list(map(int,sys.stdin.readline().split()))
    N = numbers[0]
    if numbers[0] == 0:
        break
    stack = []
    output = -1
    for n in range(1,N+1):
        now = numbers[n]
        start = n
        while(stack):
            if stack[-1][0] > now:
                output = max(output, stack[-1][0] * (n-stack[-1][1]))
                start = stack[-1][1]
                stack.pop()
            else:
                break
        stack.append([now,start])
    for i in range(len(stack)):
        output = max(output, stack[i][0] * (N+1-stack[i][1]))

    print(output)