C++로 스트리밍 정수를 서로소 구간(Disjoint Intervals)으로 요약하는 방법

문제 개요

정수로 이루어진 데이터 스트림(a1, a2, ..., an, ...)이 입력된다고 가정해 보겠습니다. 우리는 지금까지 확인한 모든 숫자를 서로 겹치지 않는 구간(disjoint intervals)의 목록 형태로 요약해야 합니다.

예를 들어, 입력 정수가 1, 3, 8, 2, 7, ... 순서로 들어온다면 각 시점의 요약 결과는 다음과 같습니다.

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [8, 8]
[1, 3], [8, 8]
[1, 3], [7, 8]

2가 들어오면 기존의 [1, 1]과 [3, 3] 사이의 빈 공간이 채워져 하나의 구간 [1, 3]으로 병합되고, 7이 들어오면 [8, 8]과 연결되어 [7, 8]이 되는 방식입니다.

해결 접근 방법

이 문제는 정렬된 집합(std::set)을 활용하면 깔끔하게 해결할 수 있습니다. std::set은 중복을 허용하지 않으면서 항상 정렬된 상태를 유지하므로, 구간 병합 로직이 단순해집니다. 알고리즘 단계는 다음과 같습니다.

정수를 저장할 집합 nums를 생성합니다.
addNum(num) 메서드가 호출되면 입력받은 num을 집합 nums에 삽입합니다. (집합이 자동으로 정렬 및 중복 제거를 처리합니다.)
getIntervals() 메서드에서는 다음 작업을 수행합니다.
- 결과를 담을 2차원 배열 ret을 정의합니다.
- 집합의 첫 번째 원소부터 끝까지 반복자(it)를 이동하며 탐색합니다.
- 현재 값이 x일 때, ret이 비어 있거나 마지막 구간의 끝값 + 1이 x보다 작다면 새 구간 {x, x}를 추가합니다.
- 그렇지 않다면(현재 값이 직전 값과 연속된다면) 마지막 구간의 끝값을 1 증가시켜 구간을 확장합니다.
- 모든 원소를 처리한 후 ret을 반환합니다.

집합은 항상 오름차순으로 정렬되어 있으므로, 인접한 두 값이 연속적(차이가 1)인지만 확인하면 자연스럽게 구간이 병합됩니다.

C++ 구현 예제

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class SummaryRanges {
   public:
   set <int> nums;
   int low, high;
   SummaryRanges() {
      low = INT_MAX;
      high = INT_MIN;
   }
   void addNum(int val) {
      nums.insert(val);
   }
   vector<vector<int>> getIntervals() {
      vector < vector <int> > ret;
      set <int> :: iterator it = nums.begin();
      while(it != nums.end()){
         int x = *it;
         if(ret.empty() || ret.back()[1] + 1 < x){
            ret.push_back({x, x});
         } else {
            ret.back()[1]++;
         }
         it++;
      }
      return ret;
   }
};
main(){
   SummaryRanges ob;
   ob.addNum(1);
   print_vector(ob.getIntervals());
   ob.addNum(3);
   print_vector(ob.getIntervals());
   ob.addNum(8);
   print_vector(ob.getIntervals());
   ob.addNum(2);
   print_vector(ob.getIntervals());
   ob.addNum(7);
   print_vector(ob.getIntervals());
}

입력

클래스를 초기화한 후, 한 번에 하나씩 원소를 삽입하면서 구간 변화를 확인합니다.
삽입되는 원소는 [1, 3, 8, 2, 7] 입니다.

출력

[[1, 1]]
[[1, 1],[3, 3]]
[[1, 1],[3, 3],[8, 8]]
[[1, 3],[8, 8]]
[[1, 3],[7, 8]]

복잡도 분석

addNum: std::set의 삽입 연산이므로 O(log n)의 시간 복잡도를 가집니다.
getIntervals: 집합의 모든 원소를 한 번씩 순회하므로 O(n)의 시간 복잡도를 가집니다.
공간 복잡도: 저장된 숫자의 개수 n에 비례하여 O(n)의 추가 공간이 필요합니다.