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

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

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

문제 요약 : 히스토그램의 개수n과 높이를 나타내는 정수들이 주어졌다. n이 0이 나오기 전까지 히스토그램 내부에 가장 넓이가 큰 직사각형의 크기를 구해라.

 

 

히스토그램과 거의 똑같은 문제!

 

풀이 )

풀이의 흐름

1. 입력값 read를 받아 histogram함수에 넣어준다.
   1. read[0]은 직사각형의 개수 N
   2. read[1:]은 각 직사각형의 높이
2. histogram함수를 실행한다.
   1. read에 0을 추가해주는 이유는, 마지막까지 스택에 있는 값을 전부 빼내기 위함이다.
3. for문을 N+1만큼 돌린다.(0을 추가했기 때문)
4. start에 i 값을 준다.
5. 만일 스택에 값이 있다면, top의 값과 height값을 비교한다.
6. 값이 크거나 같다면, 스택 top에 있는 값은 더이상 사각형을 확장시키지 못한다는 것을 의미한다.
   1. 고로 사각형의 넓이를 구하여 answer에 넣어준다.
   2. 사각형의 가로는 현재 인덱스 값에서 top의 start 값을 빼서 구한다.
   3. 세로값은 top의 값을 그대로 사용한다.
7. stack에 start와 vlaue값을 넣어준다.
   1. 이때, start값을 넣어주는이유는 6번의 과정때문이다.
   2. 6번의 과정을 통해 start는 현재 value보다 더 큰 값들의 시작점을 저장하고 있다.
8. answer을 출력한다.
9. N값으로 0이 나올때까지 위의 일을 반복한다.

# 히스토그램에서 가장 큰 직사각형
import sys
input = sys.stdin.readline

def histogram(N, read):
    stack = []
    answer = 0
    read.append(0)

    for i in range(N+1):
        value = read[i]
        start = i
        while stack and stack[-1][1] >= value :
            start, height = stack.pop()
            answer = max(answer, (i-start)*height)
        stack.append([start, value])
    
    print(answer)

while True :
    read = list(map(int,input().split(' ')))
    N = read[0]
    if N == 0 :
        break
    histogram(N, read[1:])

1725번 히스토그램을 복습하고자 비슷한 문제를 다시 풀어보았다.

값을 input으로 받아와서 바로 실행하는 것이 아닌, 히스토그램의 높이값을 다 받아온 상태에서 함수를 돌렸기 때문에 while stack으로 함수를 비워줄 필요 없이 read에 0을 추가하여 계산하였다.