[Python/파이썬] 백준 1863번 스카이라인 쉬운거

1863번: 스카이라인 쉬운거

 

문제

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

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

 

 

입력

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

출력

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

코드

import sys
input = sys.stdin.readline

n = int(input())
skyline = []
for _ in range(n):
    skyline.append(list(map(int, input().split())))

building = []
ans = 0
for i in range(n):
    while building:
        if building[-1] > skyline[i][1]:
            building.pop()
            ans += 1
        elif building[-1] == skyline[i][1]:
            building.pop()
            break
        else:
            break
    building.append(skyline[i][1])

while building:
    a = building.pop()
    if a != 0:
        ans += 1
        
print(ans)

builing 스택에 건물들의 높이를 저장하는데 새로 들어온 건물의 높이(skyline[i][1])가 현재 builing 스택의 top에 저장된 높이(building[-1])보다 낮다면

그림에서 빨간색으로 표시된 부분과 같은 상황이다. 즉, 하나의 건물이 완성됐다는 이야기이므로 building 스택의 top을 pop해주고 ans의 값을 1 증가시켜준다. skyline[i][1]과 building[-1]이 같다면 그건 같은 건물이라는이야기이므로 pop만 해주고 ans의 값은 증가시켜주지 않고 while문을 탈출한다. while문 탈출 후에는 skyline[i][1]의 값을 building 스택에 넣어준다.

마지막에는 building 스택에 남은 빌딩들을 처리해주는데 0은 빌딩이 아니라 그냥 바닥이므로 0이 아닐때만 ans의 값을 증가시키며 pop해준다.