<Hard> The Skyline Problem (LeetCode : C#)

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

📕 문제 설명

skyline은 모든 빌딩이 합쳐져서 보이는 외곽선을 의미한다. (예제 그림 참고)

빌딩의 정보는 다음과 같이 주어진다.
buildings[i] = [left_i, right_i, height_i]

left_i: i번째 빌딩의 왼쪽 edge coordinate의 x 값
right_i: i번째 빌딩의 오른쪽 edge coordinate의 x 값
height_i: i번째 빌딩의 높이

모든 빌딩은 땅에 닿아있고, 직사각형이라 가정한다.
skyline은 x좌표 기준으로 정렬된 key points들의 리스트로 나타내진다. skyline 끝나는 지점은 y 값 0을 가진다. leftmost와 rightmost 사이의 빌딩들이 skyline 외곽선에 포함된다.

skyline에서 연속적인 height를 가지는 가로 선은 없다. 예를 들어 5의 높이를 가지는 3가지 line이 있다면 그것은 합쳐서 결과에 표현된다.
[2 3],[4 5],[7 5],[11 5],[12 7]. (x)
[2 3],[4 5],[12 7]. (o)

• Input
  빌딩 정보
• Output
  skyline 정보

예제

풀이

1) 모든 x 값 저장
2) x값 정렬해두고 빌딩들의 x 범위에 해당되는 x 값이라면 그 중 가장 높은 높이 가져온 후 answer에 저장

public class Solution {
    public IList<IList<int>> GetSkyline(int[][] buildings) {
        HashSet<int> set = new HashSet<int>();
        foreach(var building in buildings)
        {
            set.Add(building[0]); 
            set.Add(building[1]);
        }

        var answer = new List<IList<int>>();
        int max = 0; 
        foreach(var pos in set.OrderBy(x=>x))
        {
            max = 0;
            foreach(var building in buildings)
            {
                if(pos >= building[0] && pos < building[1]) // 현재 position x 를 포함하는 건물이면 
                {
                    max = Math.Max(max, building[2]); // 현재 position x 값 기준 가장 높은 높이 가져오기
                }
            }

            if(answer.Count == 0 || answer.Last()[1] != max) // 같은 높이면 pass
            {
                answer.Add(new int[]{pos, max});
            }
        }
            
        return answer;
    }
}

결과