[백준 6198] 옥상 정원 꾸미기 (Gold 5)

문제

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

접근

• 스택 기법 중 하아니 monotone stack 알고리즘으로 접근함. 간단히 말하면 스택 원소를 오름차순, 또는 내림차순으로 유지 시켜주는 알고리즘이다. (관련 링크: https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/)
• 즉 내림차순으로 스택을 유지 시켜주면서 빌딩을 기준으로 반복문을 돌아 옥상을 볼 수 있는 빌딩들을 스택에 저장해 놓는 것이 포인트다.
• 이를 스택의 길이 - 1로 answer에 더해준다. 아래의 예시로 스택 길이 -1을 더한 값이 답이 되는지 확인해보자.

[10] 현재 옥상을 볼 수 있는 건물이 없다. -> 0
[10, 3] 높이 10에서 높이 3 옥상을 볼 수 있다. -> 1
[10, 7] 높이 3은 높이 7에 막혀서 볼 수 있는 옥상이 없으므로 스택에서 제외한다. 이 후의 스택에서는 높이 10에서 높이 7의 옥상을 볼 수 있다. -> 1
[10, 7, 4] 높이 10에서 높이 4와 높이 7의의 옥상 보기 가능하지만, 높이 7은 위에서 계산했으므로 제외한다. 그리고 높이 7에서 높이 4의 옥상보기가 가능하다. -> 2
[12] 높이 10, 7, 4의 빌딩은 모두 높이 12의 건물에 막힌다. 모두 스택에서 제외한다. 이 후의 스택에서는 옥상을 볼 수 있는 건물이 없다 -> 0
[12, 2] 높이 12에서 높이 2의 옥상을 볼 수 있다. -> 1

Code

import sys

n = int(sys.stdin.readline())
answer = 0
buildings = []
stack = []

for i in range(n):
   h = int(sys.stdin.readline())
   buildings.append(h)

for b in buildings:
    while stack and stack[-1] <= b:
        stack.pop()
    stack.append(b)
    answer += len(stack)-1
print(answer)