[Python] BOJ 6198 : 옥상 정원 꾸미기

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

요구사항

• 시간 제한 1초
  • 빌당의 개수가 80,000개 이중 for문으로 확인해버리면 시간초과 가능성이 높다. 
• 메모리제한 128MB 
• 관리인들이 옥상 정원을 확인할 수 있는 총 빌딩의 수를 구해라.

설계

• 이중 for문으로 구현하면 편하겠다. 더 이상 생각이 안난다. 갇혀버렸다. 

• 위와 같은 방식을 이해하거나 실제로 건물을 stack 에 넣어보면서 가시적으로 비교하면 좋다.

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

# 건물의 개수 입력
N = int(input())
# 각 건물의 높이를 입력받음
building_heights = [int(input()) for _ in range(N)]

stack = []
result = 0

for building_height in building_heights:
    # 현재 건물 높이보다 같거나 낮은 건물들은 스택에서 제거
    while stack and stack[-1] <= building_height:
        stack.pop()
    
    # 현재 건물은 스택에 추가
    stack.append(building_height)
    
    # 스택에 남아있는 건물들은 현재 건물보다 높은 건물들이므로
    # 자기 자신을 제외한 나머지를 결과에 더함
    result += len(stack) - 1

print(result)