[LeetCode] 218. The Skyline Problem

😎풀이

1. 이벤트 배열을 생성하여 건물의 시작점, 높이, 진입점 여부를 기록한다.
2. 기록된 이벤트 배열을 정렬한다.
   2-1. X 좌표를 최우선적으로 비교하여 오름차 순으로 정렬한다.
   2-2. X 좌표가 같다면 높이를 기준으로 정렬한다.
   2-3. 이 때, 건물의 진입점이라면 높이를 내림차 순으로 정렬한다.
   2-4. 건물의 진입점이 아니라면 높이를 오름차 순으로 정렬한다.
3. Map 자료구조를 선언한다.
4. 이벤트 배열을 순회한다.
   4-1. 진입점일 경우 해당 건물의 높이에 1을 더한다.
   4-2. 진입점이 아닐 경우 해당 건물 높이에 1을 뺀다.
   4-3. 매 순회 시 건물의 최대 높이를 기록하고, 현재 순회중인 건물 높이와 비교하여 다를 경우 result에 현재 건물의 X 좌표와 높이를 추가한다.
   4-4. 최대 높이를 갱신한다.
5. result를 반환한다.

function getSkyline(buildings: number[][]): number[][] {
    type Event = [x: number, height: number, isEntering: boolean];
    
    let events: Event[] = [];
    
    // 이벤트 배열 생성 (건물의 시작점과 끝점)
    for (const [left, right, height] of buildings) {
        events.push([left, height, true]);  // 건물 시작
        events.push([right, height, false]); // 건물 종료
    }
    
    events.sort((a, b) => {
        const [aX, aY, aE] = a;
        const [bX, bY, bE] = b;

        if (aX !== bX) return aX - bX; // x 좌표 기준 정렬

        // 건물 시작 이벤트(true)는 내림차순, 종료 이벤트(false)는 오름차순
        if (aE && bE) return bY - aY; // 시작 이벤트는 높이 큰 순으로
        if (!aE && !bE) return aY - bY; // 종료 이벤트는 높이 작은 순으로

        return aE ? -1 : 1; // 시작 이벤트가 종료 이벤트보다 먼저 오도록 배치
    });
    
    let result: number[][] = [];
    let heights: Map<number, number> = new Map();
    let prevMaxHeight = 0;
    
    for (const [x, height, isEntering] of events) {
        if (isEntering) {
            heights.set(height, (heights.get(height) || 0) + 1);
        } else {
            if (heights.get(height) === 1) {
                heights.delete(height);
            } else {
                heights.set(height, heights.get(height)! - 1);
            }
        }
        
        let currentMaxHeight = Math.max(...heights.keys(), heights.size)
        
        if (currentMaxHeight !== prevMaxHeight) {
            result.push([x, currentMaxHeight]);
            prevMaxHeight = currentMaxHeight;
        }
    }
    
    return result;
}