백준 6549번: 히스토그램에서 가장 큰 직사각형 - 스택 (Python)

접근

문제 설명에서 스택과 분할정복 두가지 방법 모두로 풀 수 있다고 하여 먼저 스택 방법으로 시도해 보았다.

코드를 보면서 설명하는 것이 이해하기 쉬울듯 하여 코드에 주석으로 접근 방법을 표시하였다.

이 문제는 분할 정복 알고리즘으로도 해결할 수 있는데 이 방법은 아래의 글에 적어두었다.

2021.04.03 - [코딩/백준 (Python)] - 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python)

백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python)

코드

import sys

while 1:
    n, *temp = list(map(int, sys.stdin.readline().split()))
    if n == 0:
        break
    histogram = [0] + temp + [0]
    checked = [0]
    area = 0

    for i in range(1, n + 2):
        # 저장된 높이보다 현재 높이가 낮을 경우, while에 진입하며
        # 이전에 저장된 area (저장된 높이에서의 area)와 현재의 area를 비교한다.
        # 두 값 중 큰 값이 새로운 area에 저장되게 된다.
        while checked and histogram[checked[-1]] > histogram[i]:
            current = checked.pop()
            area = max(area, (i - 1 - checked[-1]) * histogram[current])
        checked.append(i)
    print(area)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!