<Hard> Data Stream as Disjoint Intervals (LeetCode : C#)

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

📕 문제 설명

양의 정수로 구성된 데이터 스트림이 들어올 때 disjoint interval 리스트로 나타내야 한다.

두 interval에 공통 요소가 없을 때 disjoint하다고 본다.

다음을 만족하는 SummaryRanges 클래스 구현하기
1. empty stream 오브젝트 초기화
2. void addNum(int value) 함수 구현 -> stream에 value 더하는 것
3. int[][] getIntervals() 함수 구현 -> stream에서 [start_i, end_i] 리스트 반환하기

• Input
  SummaryRanges의 함수들
• Output
  SummaryRanges 클래스 구현하기

예제

풀이

sorted set으로 중복 제거한 정렬된 자료구조를 사용해 매번 값이 들어올때 붙어있는 것이면 거기에 맞게 interval를 갱신하고, 그 외에는 interval를 분리하는 식으로 해서 구현했다.

public class SummaryRanges {
    SortedSet<int> sortedSet;

    public SummaryRanges() 
    {
        sortedSet = new SortedSet<int>();
    }
    
    public void AddNum(int value) 
    {
        sortedSet.Add(value);
    }
    
    public int[][] GetIntervals() 
    {
        List<int[]> list = new List<int[]>();
        if (sortedSet.Count == 0) return list.ToArray();
    
        // set이 비어있지 않으면 interval 구하기 
        int begin = -1;
        int end = -1;
        foreach (int x in sortedSet)
        {
            if (begin == -1)
            {
                begin = x;
                end = x;
            }
            else if (x == end + 1) // 한칸차이나면 앞 interval로 설정해주기 ex) [1,1] -> [1,2]
            {
                end = x;
            }
            else
            {
                list.Add(new int[2] { begin, end });
                begin = x;
                end = x;
            }
        }
        
        list.Add(new int[2] { begin, end });

        return list.ToArray();
    }
}

결과