백준 1863 스카이라인 쉬운거 Python

🐸 문제 정보

1863번: 스카이라인 쉬운거

 

🤖 알고리즘

스택

 

⏱️ 풀이 시간

23.55m

 

📝 풀이

확실히 닉값하는(?) 문제였다. 골드 4 치고는 쉬운...

그림을 그리면서 풀어봤더니 어렵지 않게 이해가 됐다.

1. 우선 입력값을 받되, y값만 신경쓰면 된다.
2. 이 y를 스택에 담아주는데, 아래 세 가지 조건에 따라 res 값 처리가 달라진다.
   • 스택의 마지막 값보다 큰 값인 경우
     • 새로운 건물이므로, res에 1을 더한다
   • 스택의 마지막 값보다 작은 값이고, 현재 스택에 존재하지 않는 경우
     • y가 스택에서 가장 큰 값이 되도록 pop한다.
     • 새로운 건물이므로, res에 1을 더한다.
   • 스택의 마지막 값보다 작은 값이고, 현재 스택에 존재하는 경우
     
     • y가 스택에서 가장 큰 값이 되도록 pop한다.
     • 이미 있던 건물이기 떄문에, res는 건들지 않는다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

stack = [0]
res = 0

def remove(target):
    global res
    while stack and (target < stack[-1]):
        stack.pop()
    if stack and stack[-1] != target:
        res += 1
    stack.append(target)

for _ in range(int(input().rstrip())):
    x, y = list(map(int, input().rstrip().split()))
    if stack[-1] < y:
        res += 1
        stack.append(y)
    else:
        remove(y)

print(res)