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

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

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

입력은 여러 테스트 케이스로 구성됩니다.

각 테스트 케이스는 한 줄로 구성되며 직사각형의 수 n이 먼저 주어집니다.

(1 ≤ n ≤ 100,000) n 정수 h1, …, hn (0 ≤ hi ≤

'추천 관련글,

www.acmicpc.net

문제 요약: 히스토그램의 수 n과 높이를 나타내는 정수가 주어집니다.

n이 0으로 돌아가기 전에 히스토그램 내에서 가장 큰 영역 사각형의 크기를 찾습니다.

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

해결책)

솔루션의 흐름

읽은 입력 값을 받아 히스토그램 기능에 삽입합니다.
1. read(0)는 직사각형의 개수 N입니다.
2. read(1:)는 각 사각형의 높이입니다.
히스토그램 기능을 실행합니다.
1. 읽기에 0을 추가한 이유는 스택의 모든 값을 끝까지 팝하기 위함입니다.
N+1을 사용하여 for 문을 실행합니다(0을 추가했기 때문).
시작에 i 값을 지정하십시오.
스택에 값이 있으면 상단 값을 높이 값과 비교합니다.
값이 크거나 같으면 스택 맨 위에 있는 값이 더 이상 사각형을 확장하지 않는다는 의미입니다.
1. 따라서 직사각형의 면적을 찾아 답에 입력하십시오.
2. 사각형의 너비는 현재 인덱스 값에서 top의 시작 값을 빼서 구합니다.
3. 세로 값은 위쪽 값을 그대로 사용합니다.
스택에 시드 및 값 값을 푸시합니다.
1. 이때 시드를 넣는 이유는 6단계에 있다.
2. 6단계를 통해 start는 현재 값보다 큰 값의 시작점을 저장합니다.
답을 출력하세요
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를 확인하기 위해 비슷한 문제를 다시 풀었습니다.

값을 입력받아 바로 실행하지 않고 히스토그램 높이를 받아 실행한 함수이므로 while 스택으로 함수를 플러시하지 않고 read에 0을 더하여 계산하였다.