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

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

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

 

1. 문제 설명

분할 정복문제이지만 스택을 활용해서 문제를 풀었다.

 

2. 예

3.  코드

import sys
while True:
    input_list = list(map(int, sys.stdin.readline().split()))
    if input_list[0] == 0:
        break
    input_list.append(0)
    ret = 0
    stack = [[0, 0]]
    for i in range(1, input_list[0] + 2):
        while stack[-1][1] > input_list[i]:
            tmp_list = stack.pop()
            tmp_area = 0
            while stack[-1][1] == tmp_list[1]:
                stack.pop()
            tmp_area = max((i - 1 - stack[-1][0]) * tmp_list[1], (i - tmp_list[0]) * tmp_list[1])
            if tmp_area > ret:
                ret = tmp_area
        stack.append([i, input_list[i]])
    print(ret)

• stack은 높이가 높은 순서대로 정렬되어 있어야한다. (갑자기 떨어지는 경우에 문제가 생기기 때문)
• stack의 원소는 [i번째, i번째의 높이]의 의미를 갖고 [0, 0]으로 초기화한다. ret는 제일 큰 직사각형의 넓이이다.
• 왼쪽을 기준으로 i번째 막대를 고려하는 경우를 다뤄보자. stack의 마지막 원소의 높이가 기준막대의 높이보다 작다면 i와 그 높이를 stack에 집어넣는다.
• 한편 마지막 원소가 기준 막대보다 크다면 stack의 마지막 원소의 높이가 기준막대의 높이보다 작을때까지 pop한다.
• pop을 한 막대의 윗부분에 접하는 직사각형의 넓이를 계산하여 최대면적보다 크다면 교체한다.