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

문제

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

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

입력

첫째 줄에 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

 

문제 풀이 

이 문제는 스택 자료구조를 활용하는 전형적인 스위핑 문제이다. 

건물의 최소 개수를 구해야 한다는 점이 중요하고, 높이가 올라갔다가 내려올 때, 중간에 끊어지지 않았다면 같은 건물로 볼 수 있다는 점을 이용해야한다. 

 

그래서 스카이 라인을 왼쪽에서 오른쪽으로 훑으면서 sweep 높이의 변화를 관찰해야한다.

1. 높이가 높아질 때 : 새로운 건물이 시작된 것이다. 이 높이를 스택에 저장, 즉 push 한다.

2. 높이가 낮아질 때 : 이전에 있던 높은 건물이 끝난 것입니다. 스택에서 꺼내고(Pop), 건물 개수를 +1 한다.

3. 높이가 같을 때 : 같은 건물로 취급한다. (스택에 넣지 않고 넘어간다)

 

단계

스택에는 아직 끝나지 않은 건물의 높이를 저장한다. 

1. 입력 받은 높이 y를 확인한다. (x좌표는 건물 개수를 세는 데에는 중요하지 않다.)

2. while 반복문 : 스택의 가장 위에 있는 높이가 현재 높이 y 보다 크면, 그 건물은 끝난 것이다. 

- 스택에서 pop하고 건물 개수를 +1 시킨다.

3. 중복 체크 : while 문이 끝난 후, 스택의 top이 현재 높이와 같다면, 이미 있는 건물의 연결된 것이므로 스택에 넣지 않고 무시한다.

4. 새 건물 추가 : 현재 높이 y가 스택의 top보다 크고, y>0 이라면 새로운 건물이므로 스택에 push 한다. 

5. 마무리 : 모든 입력을 처리한 후, 스택에 남아있는 건물들의 개수를 결과값에 더해준다. 

 

예시로 이해하기

입력: 1, 2, 1, 3, 1 (높이만 나열)

1. 1: 스택 [1] (새 건물)
2. 2: 2 > 1이므로 스택 [1, 2] (새 건물)
3. 1: 현재 높이가 1인데 스택 top은 2입니다.
   • 2는 끝났으므로 pop. 건물+1. 스택 [1]
   • 이제 top이 1입니다. 현재 높이 1과 같으므로 아무것도 안 함 (연결됨).
4. 3: 3 > 1이므로 스택 [1, 3] (새 건물)
5. 1: 현재 높이가 1인데 스택 top은 3입니다.
   • 3은 끝났으므로 pop. 건물+1. 스택 [1]
   • top이 1, 현재 높이 1 같으므로 패스.
6. 종료 후 잔반 처리: 스택에 [1]이 남아있음. 건물+1.
7. 총 개수: 3개

 

코드 

import sys

# 입력 속도를 위해 sys.stdin.readline 사용
input = sys.stdin.readline

n = int(input())
stack = []
result = 0

for _ in range(n):
    x, y = map(int, input().split())
    
    # 1. 스택의 top이 현재 높이보다 높으면 건물 끝남 -> pop & count
    while stack and stack[-1] > y:
        result += 1
        stack.pop()
    
    # 2. 스택의 top이 현재 높이와 같으면 같은 건물이므로 무시
    if stack and stack[-1] == y:
        continue
        
    # 3. 스택의 top보다 현재 높이가 높으면 새 건물 -> push
    # (단, 높이가 0인 지점은 건물이 아님)
    if y > 0:
        stack.append(y)

# 4. 반복문 종료 후 스택에 남아있는 건물들 계산
result += len(stack)

print(result)