[백준 1863 🥇] 스카이라인 쉬운 거

문제

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

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

입력

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

출력

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

문제풀이

import sys

n=int(sys.stdin.readline())

stack=[]
ans=0
for _ in range(n):
    x,y=map(int, sys.stdin.readline().strip().split(' '))
    while stack and stack[-1]>y:
        stack.pop()
        ans+=1
    if y not in stack and y!=0:
        stack.append(y)

if stack:
    ans+=len(stack)

print(ans)

스택을 이용하면 쉬운 문제였다.

먼저 고도가 바뀌는 정점을 입력받을 때마다 높이 값 즉, y값보다 더 큰 값이 stack에 존재하는지, 확인하면서 y값보다 더 큰 값은 pop해주고 건물의 개수인 ans +1 해준다. stack에 y보다 더 큰 값이 존재하지 않을 때까지 반복해준다. 

(처음부터 stack에 값을 넣을 때부터 자신보다 큰 값은 모두 pop하고 값을 넣기 때문에 stack의 top을 확인해주면 된다. 즉, 값을 넣을 때마다 stack에 존재하는 값들보다 더 큰 값만 넣게 됨.)

 

그리고 y가 stack에 존재하지 않으면서 0이 아니라면 stack에 push해준다. 0인 경우엔 새로운 건물이 시작되는 것이 아니라 기존의 건물을 확정지을 수 있기만 하므로 0은 push해주면 안된다. 

 

그리고 마지막에 stack에 남은 건물의 개수를 ans에 더해준다. 

 

이러한 방식으로 알고리즘을 짜야하는 이유는 스택에 존재하는 값보다 더 큰 값이나, 같은 값은 스택에 존재하는 건물이 끝났는지 확정지을 수 없고, 스택에 존재하는 값보다 더 작은 값이 나오면 스택에 존재하는 건물들의 종점을 확정지을 수 있기 때문이다.

그림으로 설명해보자면 다음과 같다.