[복기] 1933번: 스카이라인

문제

백준 1933번: 스카이라인

나의 풀이과정(성공)

다 풀고나서 솔루션을 보니 대부분의 풀이와는 조금 다른 방식으로 푼 듯하다. 솔루션의 경우, 건물의 시작점과 끝점을 분리하여 리스트에 넣고 왼쪽부터 오른쪽으로 쓸고가면서 높이를 체크해주었는데, 나는 시작점과 끝점을 분리하지 않고 왼쪽에서 오른쪽으로 한 번, 오른쪽에서 왼쪽으로 한 번 쓸면서 높이를 체크해주었다. 시간초과가 걸릴거라 생각했는데 나름 괜찮은 속도가 나온다.

스카이라인에서 고려해야 할 예외 케이스가 3가지 존재한다. 아래 케이스 때문에 틀리는 경우가 잦으니 이를 잘 고려해서 풀어야 한다.
1. 서로 다른 건물의 시작점과 끝점이 겹치는 경우
2. 서로 다른 건물의 시작점이 같은 경우
3. 서로 다른 건물의 끝점이 같은 경우

시작점을 기준으로 오름차순 정렬 후, 왼쪽에서 오른쪽으로 쓸면서 건물의 시작점 만을 체크한다. 간단하게 건물의 시작점과 높이를 우선순위큐에 넣으면서 최고 높이를 갱신하고, 특정 건물의 시작점이 최고 높이 건물과 비교한다. 시작점이 같은 경우 높이를 기준으로 내림차순 정렬하였으니, 건물의 시작점이 같은 경우, 처음에 가장 높은 건물만 체크하고 그 다음에는 continue한다.

오른쪽에서 왼쪽으로 쓸어올 때는 끝점을 기준으로 오름차순 정렬을 한다. 이때는 단순히 건물의 최고 높이가 아니라, 건물이 끝나는 지점이기 때문에 새 건물을 만나기 이전에 가장 높은 건물의 높이를 가져와야한다. 또한 끝점이 같은 경우에 대한 처리는 이전과과 마찬가지로 해주었다.

솔루션에 관한 풀이는 너무 훌륭하게 정리한 블로그가 있어 아래에 링크해두었다.

전체 코드

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

n = int(input())
buildings = [list(map(int, input().split())) for _ in range(n)]
buildings.sort(key=lambda x: (x[0], -x[1]))

answer_heap = [] ## 정답 우선순위 큐

heap = []
for building in buildings: ## 왼쪽에서 오른쪽으로 스위핑
    while heap and heap[0][1] < building[0]:
        heappop(heap)
    
    if heap:
        if answer_heap[-1][0] == building[0]: ## 시작점이 같은 경우
            continue
        if -heap[0][0] < building[1]:
            heappush(answer_heap, (building[0], building[1]))
    else:
        heappush(answer_heap, (building[0], building[1]))

    heappush(heap, (-building[1], building[2]))


buildings.sort(key=lambda x: (x[2], -x[1])) ## 끝점을 기준으로 정렬렬
heap = []
for building in buildings[::-1]: ## 오른쪽에서 왼쪽으로 스위핑
    while heap and heap[0][1] > building[2]:
        heappop(heap)
    
    if heap:
        if answer_heap[-1][0] == building[2]: ## 끝점이 같은 경우
            continue
        if -heap[0][0] < building[1]:
            heappush(answer_heap, (building[2], -heap[0][0]))
    else:
        heappush(answer_heap, (building[2], 0))
    
    heappush(heap, (-building[1], building[0]))

while answer_heap:
    print(*heappop(answer_heap), end=' ')

솔루션: 우선순위 큐 + set

스카이라인 풀이

set 자료형을 사용해 이미 지나간 건물을 체크한다. 깔끔하게 구현된 모습이다.

import sys, heapq

n = int(sys.stdin.readline())
arr = []
height = [0] * n
q = []

end = [0] * n
check = set()
for i in range(n):
    a, b, c = map(int, sys.stdin.readline().split())
    arr.append((a, i, 1))
    arr.append((c, i, -1))
    height[i] = b
    end[i] = c

arr.sort(key=lambda x : (x[0], -x[2], -height[x[1]]))

now = 0
ans = []
for i in range(len(arr)):
    point, idx, dir = arr[i]
    
    if dir == 1:
        if now < height[idx]:
            now = height[idx]
            ans.append((point, now))
        heapq.heappush(q, (-height[idx], end[idx]))
    else:
        check.add(point)
        while q:
            if q[0][1] not in check:
                break
            heapq.heappop(q)
        
        if not q:
            if now:
                now = 0
                ans.append((point, now))
        else:
            if -q[0][0] != now:
                now = -q[0][0]
                ans.append((point, now))

for i in ans:
    print(i[0], i[1], end=' ')