백준 6549 히스토그램에서 가장 큰 직사각형 파이썬

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

 

예제 입력	예제 출력
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0	8 4000

 

문제 바로가기

---

문제 풀이

가장 큰 직사각형을 구해야 함으로, 지금의 길이가 이전 길이보다 길다면 스택에 넣는 방식으로 구현했다. 그렇게 하나씩 넣다가 이전보다 짧은 길이가 나타나면 현재까지 스택에 들어있는 값들을 가지고 만들 수 있는 가장 큰 넓이를 구한다.

 

풀이 과정

 

전체 코드

import sys
input = sys.stdin.readline

while True:
    values = list(map(int, input().split()))
    
    # 0일 때 종료
    count = values[0]
    if count == 0:
        break
    else:
        values.pop(0)

    total_sum = 0
    stack = []

    for i in range(count):
        width = i

        # 왼쪽 > 오른쪽 일 때
        while stack and stack[-1][0] >= values[i]:
            height, width = stack.pop()
            total_sum = max(total_sum, height * (i-width))

        # 높이, 넓이
        stack.append([values[i], width])

    for h, w in stack:
        total_sum = max(total_sum, h*(count-w))

    print(total_sum)