[백준] #1863 스카이라인 쉬운거(python)

📌문제

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

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

입력

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

출력

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

예제 입력

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

예제 출력

6

백준 1863번 문제

💡Idea

스카이라인을 보고 최소 몇 개의 건물🌃이 있는지를 알아내는 문제입니다.

처음에는 입력을 다 받고, 가장 위에 있는 줄부터 하나씩 확인하면서 각 층별로 존재하는 건물의 개수를 세어 문제를 해결하고자 했습니다.

하지만 이런 식으로 문제를 풀면 고려해야 할 점이 너무 많아지기 때문에, 스택을 이용해서 문제를 풀기로 하였습니다.

1. 현재 스택의 top보다 큰 값이 입력되는 경우
   • 해당 값 높이의 새로운 건물이 생김
     ➡ 스택에 값 push
     $\;$
2. 현재 스택의 top과 같은 값이 입력되는 경우
   • 현재 스택의 top과 동일한 건물
     ➡ 아무것도 실행하지 않음
     $\;$
3. 현재 스택의 top보다 작은 값이 입력되는 경우
   • 현재 스택에 존재하는 값들 중, 입력된 값보다 큰 높이의 건물들은 더 이상 이어지지 않고 건물이 끝나게 됨
     ➡ 스택에서 입력된 값보다 큰 값들은 pop 한 뒤, 입력된 값이 스택의 top 보다 크다면 push

건물의 최소 개수는, 건물이 끝날 때마다 하나씩 추가해주고 모든 입력이 끝난 뒤 스택에 남아있는 0이 아닌 값들의 수를 더해주면 됩니다.

💻코드

• ⏰ 시간 : 56 ms / 메모리 : 31256 KB

import sys
input = sys.stdin.readline

n = int(input())
stack = []
ans = 0
for _ in range(n):
    x, y = map(int, input().split())
    if not stack or stack[-1] < y: # 스택의 top보다 입력된 값이 큰 경우
        stack.append(y)
    elif stack[-1] > y: # 스택의 top보다 입력된 값이 작은 경우
        while stack and stack[-1] > y: # 스택에 존재하는 큰 값들을 pop
            stack.pop()
            ans += 1
        if not stack or stack[-1] < y: stack.append(y)

print(ans + len([value for value in stack if value]))

📝코드 설명

위의 내용을 그대로 구현한 코드입니다.

• stack의 top보다 큰 값이 입력되면, stack에 그대로 append해줍니다.

• 만약 stack이 비어있다면, 입력된 값에 상관없이 stack에 append 해줍니다.

• stack의 top보다 작은 값이 입력되면, 입력된 값보다 큰 값들을 stack에서 pop해줍니다.
  📍 pop되는 값들은 더 이상 이어지지 않고 끊기는 건물들의 높이이므로, ans에 1씩 추가해줍니다.
  📍 pop을 마치고, stack이 비어있거나 입력된 값이 stack의 top보다 크다면 stack에 append해줍니다.
  

• ans의 값과 stack에 남아있는 0이 아닌 값들의 개수를 더해 답을 출력해줍니다.