백준 6549번 "히스토그램에서 가장 큰 직사각형"

문제

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

풀이

굉장히 오랜시간 걸려서 푼 문제....

스택을 활용하여 문제를 풀었다.
인덱스를 차례대로 스택에 넣어주다가 arr[i]값이 arr[stack[-1]](스택의 최상위)보다 작은 경우 stack에서 pop을 하고 그 값을 이용해 해당 인덱스에서 나올 수 있는 넓이의 최대값을 구해준다.
해당 인덱스에서 나올 수 있는 넓이의 최대값은 높이 X 넓이,
즉, arr[stack[-1]]과 i-stack[-1]-1(해당 인덱스의 히스토그램과 높이가 같거나 높은 연속되어있는 히스토그램의 수)를 구하여 정답 배열에 넣어주면 된다.
연산이 끝나면 정답배열에서 가장 큰수를 출력하면 된다.

해당 문제는 세그먼트 트리를 이용하여 풀 수도 있지만 아직 세그먼트 트리를 잘 못다루는 관계로.....

(한 4시간 걸려서 풀고 solved.ac에서 난이도 확인했더니 플래티넘 문제... 왠지 어렵더라니...)

Python 코드

import sys
input = sys.stdin.readline

while 1:
  n, *arr = list(map(int, input().split()))

  if n == 0:
    break

  stack = []
  answer = []

  for i in range(n):
    while stack and arr[i] < arr[stack[-1]]:
      idx = stack.pop()
      try:
        answer.append(arr[idx]*(i-stack[-1]-1))
      except:
        answer.append(arr[idx]*i)
    stack.append(i)

  # 남은 스택의 처리를 위한 코드
  while stack:
    idx = stack.pop()
    try:
      answer.append(arr[idx]*(n-stack[-1]-1))
    except:
      answer.append(arr[idx]*n)

  print(max(answer))