❓ Problem

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

🤔 How

• 2중 반복문으로 풀려했으나 시간부족으로 스택으로 접근하였다.
• 건물의 높이정보를 담은 building 배열 그리고 빌딩을 순회하며 stack에 저장하되 기존스택에서 현재들어온 빌딩의 크기보다 작거나 같다면 pop으로 스택을 비워준다.

❗ Solve

# 옥상정원꾸미기
import sys
from collections import deque
input = sys.stdin.readline

if __name__ == "__main__":
    buildings = [int(input()) for _ in range(int(input()))]
    stack = []
    answer = 0
    for b in buildings:
        while stack and stack[-1] <= b:
            stack.pop()
        answer += len(stack)
        stack.append(b)
    print(answer)
    pass