[백준] 1863번 - 스카이라인 쉬운거 Python

문제

---

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

입력

---

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.

출력

---

첫 줄에 최소 건물 개수를 출력한다.

예제 입력 1

---

10
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

예제 출력 1

---

6

풀이

---

import sys

input = sys.stdin.readline

n = int(input().rstrip())

stack = []
answer = 0

for _ in range(n):
    x,y = map(int,input().rstrip().split())
    while len(stack)>0 and stack[-1] >y:
        answer+=1
        stack.pop()
    if len(stack)>0 and stack[-1] == y:
        continue
    stack.append(y)

while len(stack)>0:
    if stack[-1] >0:
        answer+=1
    stack.pop()

print(answer)

정리

---

• y가 변하는 지점들을 확인하면서 stack에 넣거나 뺀다.
• y가 같다면 stack에 넣지 않고, stack의 top보다 작으면 건물의 개수(answer)를 1씩 증가시킨다.
• 마지막으로 stack에 남아 있는 값들을 꺼내면서 0보다 크면 건물의 개수를 1씩 증가시킨다.