1863 스카이라인 쉬운거

문제

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

1863번: 스카이라인 쉬운거

 

접근

• 건물 겉넓이, 빗물 트래핑, 주식 매매 같은 문제랑 비슷한 거 같아서 스택으로 풀이했다.

 

풀이

• 입력받은 y에 대해 스택에는 y보다 낮은 높이의 건물만 있도록 pop하면서 ans에 1씩 더한다.
• y가 스택에 있는 마지막 요소랑 같거나 0인 경우에는 스킵하고, 더 작은 경우 append한다.
• 모든 입력을 처리한 후 스택에 남아있는 원소들을 pop하면서 ans에 1씩 더한다.

n = int(input())
stack = []

ans = 0
for _ in range(n):
    x, y = map(int, input().split())

    while stack and stack[-1] > y:
        stack.pop()
        ans += 1

    if y == 0:
        continue

    if not stack or stack[-1] < y:
        stack.append(y)

while stack:
    stack.pop()
    ans += 1
print(ans)