6198번 - 옥상 정원 꾸미기

💡 시간초과를 잘 고려하고, 찬찬히 생각하는 습관을 가지자!!

import sys

input = sys.stdin.readline

N = int(input())
cnt = 0

height = [0] * N
stack = []

for i in range(N):
    
    height[i] = int(input())
    
for j in height:
    
    while stack:
        if j < stack[-1]:
            cnt += len(stack)
            break
        else:
            stack.pop()
    stack.append(j)
    
print(cnt)

• 위 문제도 생각보다 어려웠다.. 다행히 최근 풀었던 2493번 문제와 풀이 방식이 비슷하여서 도출해낼 수 있었다.
• 이 문제는 결국 전체 건물중 본인보다 큰 건물이 나오기 전까지 작은 건물이 총 몇번 나오는지를 count하는 문제였다.
• 풀이방법은 총 2가지 경우가 있다.
  => 현재 타워의 높이가 stack의 맨 위보다 작으면, stack의 크기를 더해준다. (stack의 맨위 입장에서는 본인보다 작은 빌딩이 추가되는 것임)
  => 현재 타워의 높이가 stack의 맨 위보다 크면, stack의 맨위의 것을 pop()한다. ( stack의 맨위 입장에서는 본인보다 큰 빌딩이 나오면서 역할이 사라짐)
  => 이런 과정을 거치고 난 후 본인의 빌딩을 추가한다.
• 결론적으로, 햔재 타워는 stack에 남아있는 본인보다 큰 빌딩에게 보이는 빌딩이 되는 것이기 떄문에 위 방식을 사용해서 해결하였다.