백준[1863] 스카이라인 (Python3)

어떤 것을 pop 할지를 잘못 생각해서 삽질한 문제

스택에서 없애야 할 것

건물이 더 이상 확장할 수 없는 경우, pop 한다.
입력으로 들어온 Y가 스택의 상단 T보다 작다면, (Y < stack.top())
높이 T를 가지는 건물의 범위는 거기서 끝나기 때문에, 더 이상 스택에 있을 필요가 없어진다.

스택에 넣지 말아야 할 상황

건물의 영역이 이어지는 경우, 스택에 push 하지 않는다. (Y == stack.top())
즉, 입력으로 들어온 Y가 스택의 상단 T와 같다면 스택에 넣지 않는다.
고층 건물에 대한 정보가 삭제된 후, 바뀐 스택의 상단 T가 N과 높이가 같다면, 높이 N의 건물이 계속되는 형태기 때문에, 따로 카운팅을 할 필요가 없어진다.

스택에 넣어야 하는 상황

스택이 비어있을 때와, 입력으로 들어온 Y가 스택의 상단 T보다 큰 경우(Y > stack.top())
새로운 높이의 건물이 들어왔기 때문에, Y 높이를 가진 건물들이 어디까지 확장되는지를 봐야 한다.

 

코드

import sys
from collections import deque
input = sys.stdin.readline


def main():
    N = int(input())
    stack = deque()
    ans = 0
    for _ in range(N):
        x, y = map(int, input().split())
        if not stack:
            stack.append(y)
            continue
        while stack and y < stack[-1]:
            ans += 1
            stack.pop()
        if not stack or (stack and y != stack[-1]):
            stack.append(y)
    while stack:
        if stack[-1] > 0:
            ans += 1
        stack.pop()
    print(ans)


if __name__ == '__main__':
    main()