218. The Skyline Problem

[zeikar]

Problem link

https://leetcode.com/problems/the-skyline-problem/

Problem Summary

빌딩이 주어질 때 스카이라인을 출력하는 문제.

Solution

상당히 빡센 문제이다.
heap (pq)를 쓴다는 것을 알고 봐도 쉽지 않음.

일단 왼쪽부터 오른쪽으로 하나씩 스캔하는 방식으로 진행하면서 현재까지 겹쳐있는 빌딩의 높이를 관리해주면 풀 수 있다.

스캔은 빌딩 시작과 끝을 기준으로 해야 하므로 주어진 빌딩 배열을 분해해주자. 그리고 현재까지 빌딩 높이 관리는 가장 높은 빌딩이 우선되어야 하므로 pq를 통해 관리해주면 된다.

상세 구현

0. 정렬: x좌표를 기준으로 정렬하지만 같은 경우 처리가 필요한데, 빌딩 시작 이벤트는 높은 빌딩부터 처리, 빌딩 끝 이벤트는 낮은 빌딩부터 처리해야 겹치는 빌딩을 잘 핸들링할 수 있다.
1. 빌딩 시작: 스캔하면서 현재까지 빌딩들보다 더 높게 나온 경우 pq에 추가하고 스카이라인에 추가한다. 더 낮은 경우 pq에만 넣고 스카이라인에 추가는 하지 않는다.
2. 빌딩 끝: 끝난 빌딩이 더 낮은 경우 일단 무시한다. (나중에 제거) 끝난 빌딩이 같거나 더 높은 경우 남아있는 빌딩들을 pq에서 제거하는데 현재 빌딩의 높이를 보고 더 작은 빌딩이 이전에 끝난 경우 필요가 없으므로 pq에서 싹 정리해준다. 그리고 스카이라인에 추가하는데 이전 스카이라인의 높이와 같으면 추가하지 않는다. (머지되어 한개로 간주)

코드가 좀 지저분하지만 일단 정답이긴 하니 ㅋㅋ 올려둠. 시간복잡도는 O(n logn)

Source Code

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        lines = []
        for building in buildings:
            lines.append([building[0], -building[2], building[1]])
            lines.append([building[1], building[2], 0])
        lines.sort()
        print(lines)

        ans = []
        heights = [[0, inf]]
        for line in lines:
            [x, h, r] = line

            if r == 0:
                if -heights[0][0] > h:
                    continue
                                    
                while -heights[0][0] <= h and heights[0][1] <= x:
                    heapq.heappop(heights)

                if ans[-1][1] != -heights[0][0]:
                    ans.append([x, -heights[0][0]])
            else:
                h *= -1

                if -heights[0][0] >= h:
                    heapq.heappush(heights, [-h, r])
                    continue
            
                heapq.heappush(heights, [-h, r])
                ans.append([x, h])

        return ans