[백준 1725번] 히스토그램 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N = int(input())

result = 0
hq = []
for i in range(N):
  h = int(input())
  heappush(hq,(-h,i))
  while hq and -hq[0][0]>h:
    h1,i1 = heappop(hq)
    result = max(result,-h1*(i-i1))
    heappush(hq,(-h,i1))
while hq:
  h,i = heappop(hq)
  result = max(result,-h*(N-i))
print(result)

우선순위 큐를 이용해서 해결하였다.

 

보통 세그먼트 트리, 분할정복을 이용해서 푼다고 하는데, 그 방법으로 어떻게 풀어야 할지 아이디어가 도저히 안떠올라서 못풀다가 다른 방식을 시도했더니 풀 수 있었다.

 

알고리즘을 설명하면,

1. 최대힙에 높이와 인덱스를 튜플로 저장한다. (높이는 음수로 저장)

2. 현재의 입력받은 높이보다 높이가 더 높은 값들을 모두 pop 한 뒤 result를 넓이(index차이 * 높이)로 갱신한다.

3. 현재의 입력받은 높이,원래 인덱스로 재삽입한다.

4. 마지막에는 힙큐의 모든 입력을 pop하고 result를 갱신한다.

5. 최댓값을 출력한다.

 

구현은 매우 간단하지만 다른 풀이에 비해 제출시간이 오래 걸린다는 단점이 있었다.

세그먼트 트리와 분할정복을 이용한 풀이도 고민해보아야겠다.

 

오늘의 교훈) 세그먼트 트리와 분할정복을 이용해서 히스토그램을 풀어보자