[백준] 1725 히스토그램 - 파이썬

문제

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

1725번: 히스토그램

 

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

 

---

풀이

 

나는 최대힙을 사용하여 브루트포스로 풀었다.

새로 입력되는 히스토그램 막대의 길이가 예전에 들어왔던것보다 작으면,

현재 들어온 막대의 전 x축 가로길이에 예전에 들어왔던 것의 x축을 빼서 사각형 가로길이를 구하고

이전 높이를 곱하여 maxsize를 업데이트해준다.

마지막 히스토그램은 따로 조건처리를 해준다.

 

 

import sys
import heapq
input = sys.stdin.readline

n = int(input())
height = int(input())
calculating = [(-height, 0)]

maxsize = 0
for i in range(1, n):
    height = int(input())
    height *= -1
    if i == n-1:
        heapq.heappush(calculating, (height, i))
        while calculating:
            ch, cx = heapq.heappop(calculating)
            if -height >= -ch:
                maxsize = max(maxsize, (i+1-cx)*-ch)
            else:
                maxsize = max(maxsize, (i-cx)*-ch, (i+1-cx)*-height)
    else:
        while calculating and -calculating[0][0] > -height:
            ch, cx = heapq.heappop(calculating)
            maxsize = max(maxsize, (i-cx)*-ch)
            heapq.heappush(calculating, (height, cx))
        heapq.heappush(calculating, (height, i))

print(maxsize)

 

근데 문제 분류가 아래와 같이 되어있었다.

• 자료 구조
• 세그먼트 트리
• 분할 정복
• 스택

난 이렇게 안풀었기때문에 다른 분의 풀이를 봐보았다.

https://hooongs.tistory.com/330

[백준6549번] 히스토그램에서 가장 큰 직사각형 / Python3

생각해보니 스택을 이용하면 굳이 힙을 이용할 필요가 없긴 했다.

내 코드는 약 O(NlogN)일거같은데 저렇게 하면 O(N)으로 될 듯..?!