💡 문제
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좌표와 그 지점에서의 높이를 출력한다.
💭 접근
이 문제를 해결하기 위해 다음과 같은 단계를 거친다.
- 건물의 정보를 건물의 시작점과 끝점을 따로 저장
for i in range(n):
l, h, r = map(int, input().split())
buildings.append((l, i, 1)) # 건물 시작 좌표, 건물 인덱스, 시작점(1)
buildings.append((r, i, 0)) # 건물 끝 좌표, 건물 인덱스, 끝점(0)
height[i] = h # i번째 건물의 높이 저장
end[i] = r # i번째 건물의 끝 좌표 저장- 건물의 정보가 담겨있는 리스트를 아래와 같은 규칙으로 정렬
# 1. 좌표가 빠른 순
# 2. 좌표가 같다면 시작점인지
# 3. 좌표가 같고 둘다 시작점 or 끝점이라며 높이가 높은 순
buildings.sort(key=lambda x: (x[0], -x[2], -height[x[1]]))- 건물의 정보가 담겨있는 리스트를 순회하며 정답 처리
-
시작점 : 별다른 처리 없이 최대 높이만 고려하며 정답에 추가
if is_start: if max_height < height[idx]: # 현재 최대 높이보다 idx번째 건물의 높이가 더 높다면 max_height = height[idx] # 최대 높이 갱신 ans.append((cursor, max_height)) # 높이가 변했으므로 정답에 추가 heapq.heappush(q, (-height[idx], end[idx])) # 건물 정보 큐에 저장 -
끝점 : 현재 가장 높은 건물이 끝났는지 확인 후, 만약 현재 가장 높은 건물이 끝났다면 다음으로 높은 건물을 찾기 위해 이미 끝났거나, 최대 높이 갱신에 영향을 주지 않는 건물들 삭제
삭제 후 큐가 비었다면 건물이 없는 것이므로 최대 높이를 0(지면)으로 갱신
삭제 후 큐에 원소가 남아있다면 다음으로 높은 건물 높이로 최대 높이 갱신else: # 끝점 저장 check.add(cursor) # 우선순위 큐의 특성 상 q[0][1]에 가장 높은 건물의 높이와 좌표가 담겨있음 # 현재 가장 높은 건물이 끝났다면 다음으로 높은 건물을 찾기 위해 # 큐가 비거나, 아직 끝나지 않은 다음으로 높은 건물을 만날 때까지 삭제 while q: if q[0][1] not in check: break heapq.heappop(q) # 위에서 삭제 후 큐가 비었다면 if not q: # 이제 땅이므로 최대 높이 0으로 갱신 if max_height: max_height = 0 ans.append((cursor, max_height)) # 삭제 후 큐에 원소가 남아 있다면 큐의 첫번째 원소가 # 다음으로 높은 건물이므로 이 값으로 현재 최대높이 갱신 else: if -q[0][0] != max_height: max_height = -q[0][0] ans.append((cursor, max_height))이제 위 과정을 간단한 예시를 통해 이해해보자.
입력
4 1 11 5 2 6 7 3 13 9 12 7 16
먼저 입력에 대해 건물 정보 리스트에 시작점과 끝점을 나누어 저장 후, 정렬하면 다음과 같다.
buildings = [(1, 0, 1), → 건물1 시작
(2, 1, 1), → 건물2 시작
(3, 2, 1), → 건물3 시작
(5, 0, 0), → 건물1 끝
(7, 1, 0), → 건물2 끝
(9, 2, 0), → 건물3 끝
(12, 3, 1), → 건물4 시작
(16, 3, 0) → 건물4 끝]이제 위와 같이 정렬된 리스트를 순회하며 정답을 갱신해보자.
단계 1 : cursor = 1, idx = 0, is_start = 1 → 건물1 시작 (높이 11)
q= [(-11, 5)]max_height= 11 → 정답 리스트에 추가 (1, 11)
단계 2 : cursor = 2, idx = 1, is_start = 1 → 건물2 시작 (높이 6)
q= [(-11, 5), (-6, 7)]max_height= 11 → 유지 (변화 없음)
단계 3 : cursor = 3, idx = 2, is_start = 1 → 건물3 시작 (높이 13)
q= [(-13, 9), (-6, 7), (-11, 5)]max_height= 13 → 정답 리스트에 추가 (3, 13)
단계 4 : cursor = 5, idx = 0, is_start = 0 → 건물1 끝
check= {5}q[0][1]= 9 → 아직 끝나진 않은 건물이 가장 높으므로 유지
단계 5 : cursor = 7, idx = 1, is_start = 0 → 건물2 끝
check= {5, 7}q[0][1]= 9 → 아직 끝나진 않은 건물이 가장 높으므로 유지
단계 6 : cursor = 9, idx = 2, is_start = 0 → 건물2 끝
check= {5, 7, 9}q[0][1]= 9 → 끝났으므로 삭제q= [(-11, 5), (-6, 7)]q[0][1]= 5 → 끝났으므로 삭제q= [(-6, 7)]q[0][1]= 7 → 끝났으므로 삭제q= [] → 정답 리스트에 추가 (9, 0)
단계 7 : cursor = 12, idx = 3, is_start = 1 → 건물4 시작 (높이 7)
q= [(-7, 16)]max_height= 7 → 정답 리스트에 추가 (12, 7)
단계 8 : cursor = 16, idx = 3, is_start = 0 → 건물2 끝
check= {5, 7, 9, 16}q[0][1]= 16 → 끝났으므로 삭제q= [] → 정답 리스트에 추가 (16, 0)
따라서 정답은 아래와 같이 도출된다.
정답 : 1 11 3 13 9 0 12 7 16 0
📒 코드
import heapq
n = int(input())
buildings = []
height = [0 for _ in range(n)]
end = [0 for _ in range(n)]
for i in range(n):
l, h, r = map(int, input().split())
buildings.append((l, i, 1)) # 건물 시작 좌표, 건물 인덱스, 시작점(1)
buildings.append((r, i, 0)) # 건물 끝 좌표, 건물 인덱스, 끝점(0)
height[i] = h # i번째 건물의 높이 저장
end[i] = r # i번째 건물의 끝 좌표 저장
# 1. 좌표가 빠른 순
# 2. 좌표가 같다면 시작점인지
# 3. 좌표가 같고 둘다 시작점 or 끝점이라며 높이가 높은 순
buildings.sort(key=lambda x: (x[0], -x[2], -height[x[1]]))
q = [] # idx번째 건물의 높이와 끝점이 담길 우선순위 큐
ans = []
check = set() # 끝점 좌표가 담길 set
max_height = 0
for i in range(len(buildings)):
cursor, idx, is_start = buildings[i]
# 시작점이라면
if is_start:
if max_height < height[idx]: # 현재 최대 높이보다 idx번째 건물의 높이가 더 높다면
max_height = height[idx] # 최대 높이 갱신
ans.append((cursor, max_height)) # 높이가 변했으므로 정답에 추가
heapq.heappush(q, (-height[idx], end[idx])) # 건물 정보 큐에 저장
# 끝점이라면
else:
# 끝점 저장
check.add(cursor)
# 우선순위 큐의 특성 상 q[0][1]에 가장 높은 건물의 높이와 좌표가 담겨있음
# 현재 가장 높은 건물이 끝났다면 다음으로 높은 건물을 찾기 위해
# 큐가 비거나, 아직 끝나지 않은 다음으로 높은 건물을 만날 때까지 삭제
while q:
if q[0][1] not in check:
break
heapq.heappop(q)
# 위에서 삭제 후 큐가 비었다면
if not q:
# 이제 지면이므로 최대 높이 0으로 갱신
if max_height:
max_height = 0
ans.append((cursor, max_height))
# 삭제 후 큐에 원소가 남아 있다면 큐의 첫번째 원소가
# 다음으로 높은 건물이므로 이 값으로 현재 최대높이 갱신
else:
if -q[0][0] != max_height:
max_height = -q[0][0]
ans.append((cursor, max_height))
for i in ans:
print(i[0], i[1], end=' ')💭 후기
아직 우선순위 큐 사용이 익숙하지 않아서 많이 어려웠고, 풀이를 이해하는 데에도 시간이 오래 걸렸던 문제였다...
🔗 문제 출처
https://www.acmicpc.net/problem/1933
