[우선순위 큐 (고급)] LC #218 The Skyline Problem

문제 설명

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]

 

Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

 

Constraints:


문제 링크: https://leetcode.com/problems/the-skyline-problem/

핵심 아이디어

이 문제는 '스위프 라인(Sweep Line)' 알고리즘과 '우선순위 큐(Priority Queue)'를 함께 사용하는 대표적인 예시입니다. 스카이라인의 윤곽이 바뀌는 지점, 즉 'Key Point'는 건물의 왼쪽 모서리 또는 오른쪽 모서리에서만 발생한다는 점에 착안합니다.

스위프 라인 (Sweep Line) 알고리즘이란?
기하학적 문제들을 풀기 위해, 수직 또는 수평선을 왼쪽에서 오른쪽으로 (또는 위에서 아래로) 훑고 지나가면서 선과 만나는 지점의 이벤트들을 처리하는 방식입니다.

알고리즘의 단계는 다음과 같습니다.

  1. 포인트 분리 및 정렬:
    모든 빌딩 정보를 두 개의 포인트로 분리합니다: `[왼쪽 x좌표, -높이]`와 `[오른쪽 x좌표, 높이]`.
    - 왼쪽 모서리(시작점)의 높이를 음수로 만드는 이유는 두 가지입니다.
    • 정렬 시 x좌표가 같을 경우, 시작점이 끝점보다 먼저 오게 하기 위함입니다.
    • 같은 x좌표에 여러 빌딩이 겹칠 경우, 높이가 더 높은 빌딩이 먼저 처리되도록 하기 위함입니다. (예: `-15`가 `-10`보다 작으므로 먼저 옴)
    - 오른쪽 모서리(끝점)는 양수 높이를 그대로 사용합니다.
  2. 스위핑 및 높이 관리:
    정렬된 포인트들을 순서대로 순회합니다. 이때, 현재 유효한 빌딩들의 높이를 관리하기 위해 최대 힙(Max Heap) 역할을 하는 우선순위 큐를 사용합니다.
    • 포인트가 시작점(높이가 음수)이면, 해당 높이의 절댓값을 우선순위 큐에 추가합니다. 이는 새로운 빌딩이 시야에 들어왔음을 의미합니다.
    • 포인트가 끝점(높이가 양수)이면, 해당 높이를 우선순위 큐에서 제거합니다. 이는 빌딩이 시야에서 사라졌음을 의미합니다.
  3. Key Point 판별:
    각 포인트를 처리한 후, 우선순위 큐의 최댓값(가장 높은 빌딩의 높이)을 확인합니다. 이 최댓값이 이전 단계의 최댓값과 다르다면, 스카이라인의 높이가 변한 것이므로 현재 x좌표와 새로운 높이를 Key Point로 결과 리스트에 추가합니다.

코드 구현 (Java)


import java.util.*;

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<int[]> points = new ArrayList<>();
        for (int[] b : buildings) {
            points.add(new int[]{b[0], -b[2]}); // 시작점
            points.add(new int[]{b[1], b[2]});  // 끝점
        }

        // x좌표 기준으로 정렬, x가 같으면 높이 기준으로 정렬
        Collections.sort(points, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1]; // 시작점이 먼저, 높이가 높은 시작점이 먼저
            }
        });

        // 높이를 내림차순으로 관리하는 우선순위 큐 (Max Heap)
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.offer(0); // 바닥 높이
        int prevMaxHeight = 0;
        List<List<Integer>> result = new ArrayList<>();

        for (int[] point : points) {
            int x = point[0];
            int height = point[1];

            if (height < 0) { // 시작점
                pq.offer(-height);
            } else { // 끝점
                pq.remove(height);
            }

            int currentMaxHeight = pq.peek();
            if (currentMaxHeight != prevMaxHeight) {
                result.add(Arrays.asList(x, currentMaxHeight));
                prevMaxHeight = currentMaxHeight;
            }
        }

        return result;
    }
}

복잡도 분석

Interview Tip

이 문제는 여러 개념을 복합적으로 활용해야 하는 고급 문제입니다. 면접관은 문제 해결 능력뿐만 아니라, 적절한 자료구조를 선택하고 그 이유를 설명하는 능력을 보고자 합니다.