[python] 백준 1933 :: 스카이라인 (우선순위 큐)

[스카이라인]

# 문제
N개의 직사각형 모양의 건물들이 주어졌을 때, 스카이라인을 구해내는 프로그램을 작성하시오. 스카이라인은 건물 전체의 윤곽을 의미한다. 즉, 각각의 건물을 직사각형으로 표현했을 때, 그러한 직사각형들의 합집합을 구하는 문제이다.

예를 들어 직사각형 모양의 건물들이 위와 같이 주어졌다고 하자. 각각의 건물은 왼쪽 x좌표와 오른쪽 x좌표, 그리고 높이로 나타난다. 모든 건물들은 편의상 같은 높이의 지면(땅) 위에 있다고 가정하자. 위의 예에서 스카이라인을 구하면 아래와 같다.

# 입력
첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오른쪽 x좌표를 의미한다. (1 ≤ L < R ≤ 1,000,000,000, 1 ≤ H ≤ 1,000,000,000)

# 출력
첫째 줄에 스카이라인을 출력한다. 출력을 할 때에는 높이가 변하는 지점에 대해서, 그 지점의 x좌표와 그 지점에서의 높이를 출력한다.

 

풀이

전체 코드

import heapq
import sys
N = int(input())
buildings = []
end_points = []

for i in range(N):
    start, height, end = map(int, sys.stdin.readline().split())

    buildings.append((i, start, height, 0))
    buildings.append((i, end, height, 1))

    end_points.append((end))  # 어디서 끝나는지 저장

# buildings 정렬
# 정렬 우선순위 : 1) x 빠른 순, 2) start 먼저, 3) height 높은순
buildings.sort(key=lambda x: (x[1], x[3], -x[2]))

current_height = 0
end_list = set()
result = []
not_ended_building = []  # 아직 안 끝난 빌딩들

for building in buildings:
    building_idx, x, height, is_end = building

    # 시작인 경우
    if not is_end:
        if height > current_height:
            current_height = height
            result.append((x, current_height))

        # 진행중인 빌딩 최대힙에 높이랑 끝나는 x좌표 저장
        heapq.heappush(not_ended_building, (-height, end_points[building_idx]))
        continue

    end_list.add(x)

    while not_ended_building and not_ended_building[0][1] in end_list:
        heapq.heappop(not_ended_building)

    # 진행중인 빌딩이 있으면 이거로 높이 변경
    if not_ended_building:
        if current_height != -not_ended_building[0][0]:
            current_height = -not_ended_building[0][0]
            result.append((x, current_height))

    # 진행중인 빌딩이 없으면
    else:
        if current_height != 0:
            current_height = 0
            result.append((x, current_height))

for r in result:
    print(' '.join([str(r[0]), str(r[1])]), end=' ')