[백준 6198][파이썬] 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

 

stack을 사용하지 않고 이중 for문을 쓰면 시간 초과가 된다.

계산 횟수를 줄이기 위해 stack을 사용하여 '건물이 바라볼 수 있는 빌딩의 개수'가 아닌 '건물을 바라볼 수 있는 빌딩의 개수'를 구해서 더해줘야 한다. 

 

for문이 한 바퀴 돌면 stack에는 가장 왼쪽에 있는 건물의 높이가 추가된다.

이후, for문이 계속 돌면서 자신보다 왼쪽에 있는 건물들 중 stack에 남아있는 건물과 높이를 비교한다.

만약, 왼쪽에 있는 건물 중 자신보다 높은 건물이 있으면 반복을 멈추고 stack의 크기를 합계에 더한다.

 

그냥 보면 이중 for문과 비슷해 보이지만 중복 계산을 줄일 수 있다는 점에서 시간을 많이 단축할 수 있다. 

 

import sys

input = sys.stdin.readline

N = int(input())
height = []
stack = []
sum = 0

for i in range(N):
  height.append(int(input()))

for i in range(0, N):
  while len(stack) != 0 and stack[-1] <= height[i]:
    stack.pop()

  sum += len(stack)
  stack.append(height[i])

print(sum)