(Python/플5)백준알고리즘 1725번: 히스토그램

 

문제 바로가기 

 

문제:

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. 이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다. 주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력:

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력:

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

 

풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())
lst = [int(sys.stdin.readline().rstrip()) for _ in range(N)]

stk = []
max_area = 0

for i in range(N):
    while stk and lst[i] < lst[stk[-1]]: # 높이가 뚝 떨이지는 경우 앞에꺼 계산해줌
        H = lst[stk.pop()] # 높이
        width = i if not stk else i - stk[-1] - 1 # i번째 까지의 최소 높이
        area = H * width # 면적
        max_area = max(max_area, area) # 최대 면적
    stk.append(i) # 스택이 비어있으면

while stk: # 스택이 남아 있는경우
    height = lst[stk.pop()]
    width = N if not stk else N - stk[-1] - 1
    area = height * width
    max_area = max(max_area, area)

print(max_area)

 

이 전에 풀었던 히스토그램에서 가장 큰 정사각형 넓이와 같다.