책너두 - 알고리즘 챌린지[14/20]

오늘의 문제 : 히스토그램

무려 플래티넘 문제였다.

사실 플래티넘이라는 난이도에 비해 뭔가 문제가 복잡하지 않아 좋았다.

하필 이번에 나온 신작 미션 임파서블을 보러 가기 직전에 이 문제를 핸드폰으로 보고 들어갔는데,

영화를 보는 내내 코드가 어쩌구,, 소스코드가 저쩌구,, 해대는 탓에 문제가 생각나 힘들었다(톰크루즈 최고)

이 문제는 스택으로 풀 수 있다. 문제를 보고 스택을 간단히 하면 풀기 쉽겠다는 생각을 했는데, 당일 풀이에 모노토닉 스택을 올려주신 분이 계셔서 많은 걸 배웠다..!

• Monotone stack은 말 그대로 stack을 monotone, 즉 단조롭게 하는 것 입니다. 단조롭다는 것은 원소들이 증가하거나 감소하는 방향으로 존재하는 형태입니다. 쉽게 얘기해서 원소들을 특정 원소를 제거해서 정렬하는 방식입니다

import sys

n, *histo = map(int, sys.stdin.buffer.read().splitlines())

stack = []
res = 0
for now in range(n) :
    before = now
    while stack and stack[-1][1] > histo[now] :
        before, height = stack.pop()
        width = now - before
        res = max(res, width * height)

    stack.append([before, histo[now]])

# 스택이 남아있는 경우, 즉 모든 높이가 동일한 경우
while stack :
    width, height = stack.pop()
    res = max(res, (n - width) * height)

print(res)