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

https://www.acmicpc.net/problem/1863

 

# 1863 스카이라인 쉬운거

import sys
input = sys.stdin.readline

n = int(input())
buildings = [list(map(int, input().split())) for _ in range(n)]
buildings.sort() # x좌표 정렬

# 스택에 남는 건물이 없도록 마지막에 높이가 0 인 건물 추가
buildings.append([float('inf'), 0])

ans = 0
stack = [0] # 건물 높이를 저장하고 높이가 낮아질 때 pop 하여 건물 수를 셈

for x,y in buildings:
    while stack and y < stack[-1]: # 건물이 종료되는 시점
        stack.pop()
        ans += 1
    if y > stack[-1]: # 새로운 건물이 시작되는 시점
        stack.append(y)

print(ans)

 

📌 문제 요약

좌표 평면 위에 건물들의 (x, y) 좌표가 주어졌을 때,
도심의 스카이라인을 그렸을 때 생기는 건물들의 개수를 세는 문제입니다.

단, 건물들은 서로 붙어있거나 높이가 같을 수 있고, 건물 높이가 감소하면 이전 건물의 끝으로 간주합니다.

 

🧠 핵심 아이디어 — “높이 변화”만 보면 된다

문제의 본질은 x좌표를 기준으로 높이가 어떻게 변하는지를 추적하면서,
새로운 건물이 시작될 때 +1,
건물이 끝날 때 +1을 세는 것입니다.

이를 위해 스택을 사용합니다.

• stack : 지금까지 본 건물들의 “높이”를 저장
• push : 새로운 건물이 시작됨 (이전보다 높이가 높아짐)
• pop : 이전 건물이 끝남 (현재 높이보다 스택 top이 높을 때)

 

📌 왜 (inf, 0)을 넣는가?

마지막에 높이가0인 가짜 건물을 추가해줌으로써 추가적으로 스택에 남아있는 건물에 대해서 처리해줄 필요가 없다.

마지막에 0을 추가해주지 않는다면 아래 로직이 추가적으로 필요하다.

while stack and stack[-1] > 0:
    stack.pop()
    ans += 1

 

 

📌 pop을 while로 해야 하는 이유

만약 중간에 10 → 5 → 0처럼 여러 번 높이가 떨어지는 경우,
한 번의 if로는 한 층만 pop되고 나머지가 스택에 남아버립니다.
그래서 while을 써서 현재 높이보다 높은 스택의 값이 없어질 때까지 반복 pop을 해야 합니다.