[Python] 백준6198번 : 옥상 정원 꾸미기

💡문제

백준 6198번 문제 링크

🍀풀이

코드

import sys
input = sys.stdin.readline

n = int(input().strip())

h = [int(input().strip()) for _ in range(n)]
stack = []
result = 0

for i in range(n):
    while stack and stack[-1] <= h[i]:
        stack.pop()
    
    result += len(stack)
    stack.append(h[i])

print(result)

문제를 읽었을 때, 탑 문제랑 비슷할거라 생각을 해서 비슷하게 풀었다.

1. stack의 맨 위(최근에 넣은 값)와 현재 높이(h[i])를 비교
2. 현재 높이(h[i])가 스택의 맨 위보다 높으면:
   • 스택의 빌딩은 더 이상 볼 수 없음 → pop()으로 제거
   • 반복하면서 현재 높이보다 낮거나 같은 모든 값을 제거
3. 남은 스택의 크기만큼 볼 수 있는 개수를 추가

이런식으로 풀어봤다. 뭔가 풀고나면 쉬운데 풀면서는 왜 어려운지...