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

import sys
input = sys.stdin.readline

while True:
  data = [*map(int,input().split())]
  N = len(data)-1
  if N==0:
    break

  result = 0
  histogram = []
  for i in range(N):
    h = data[i+1]
    i1 = i
    while histogram and histogram[-1][0]>=h:
      h1,i1 = histogram.pop()
      result = max(result,h1*(i-i1))
    histogram.append((h,i1))
  while histogram:
    h,i = histogram.pop()
    result = max(result,h*(N-i))
  print(result)

히스토그램 [백준 1725번] 히스토그램 (Python3) (tistory.com)  문제와 똑같은 문제이다. 딱하나 차이점은 테스트케이스가 더 많기 때문에 시간초과가 약간 더 빡빡하다. 그래서 나의 전 풀이는 시간초과로 통과되지 않았다.

 

그런데 나의 전 풀이에서 개선할 수 있는 부분을 발견하였다. 스택을 쌓을 때, 굳이 우선순위 큐를 이용할 필요가 없었던 것이다.

왜냐하면 스택에서 현재의 높이보다 작은 높이를 pop 시키게 되면 결국 스택에는 높이가 오름차순으로 쌓이게 된다. 즉 어차피 스택의 마지막 부분이 가장 크기 때문에 우선순위큐로 가장 큰 높이부터 뽑을 필요가 없이 그냥 리스트의 마지막을 pop 시켜주면 된다.

 

따라서 시간복잡도 O(N)으로 구현할 수 있다.

 

해당 코드를 이전 문제인 1725번에 제출하자 제출시간이 10배이상 단축되었고, 이 문제도 빠른 속도로 통과되었다.

 

 

오늘의 교훈) 데이터를 면밀하게 탐색하여 적절한 자료구조를 고르자