C++로 구현하는 누락된 범위(Missing Ranges) 찾기 알고리즘

문제 소개

정렬된 정수 배열 nums가 주어졌다고 가정해 봅시다. 배열 원소들의 값은 닫힌 구간 [lower, upper] 안에 속하며, 우리는 이 범위 안에서 배열에 빠져 있는 숫자 구간, 즉 누락된 범위(missing ranges)를 모두 찾아야 합니다.

예를 들어 입력이 nums = [0, 1, 3, 50, 75]이고 lower = 0, upper = 99라면 출력은 다음과 같습니다.

["2", "4->49", "51->74", "76->99"]

배열에 없는 값이 하나뿐이면 "2"처럼 단일 값으로 표현되고, 4~49, 51~74, 76~99처럼 여러 값이 연속적으로 비어 있으면 "시작->끝" 형식으로 나타냅니다.

해결 접근 방법

이 문제는 현재 검사 위치를 추적하며 배열을 한 번 순회하는 방식으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.

1단계: 중복 제거 및 배열 준비

결과용 배열 nums와 중복 검사용 집합 v를 정의합니다.
입력 배열 t를 처음부터 끝까지 순회하면서, 아직 v에 없는 값이라면 집합에 추가하고 동시에 nums의 끝에도 삽입합니다. 이 과정을 통해 중복 원소가 자연스럽게 제거됩니다.

2단계: 변수 초기화

누락 구간을 저장할 문자열 배열 ret을 선언합니다.
현재 검사 중인 값을 뜻하는 curr을 lower로 설정합니다.
인덱스 i는 0, 배열 크기 n은 nums의 길이로 초기화합니다.

3단계: 범위 순회

curr이 upper 이하인 동안 다음 과정을 반복합니다.

값이 존재하는 경우: i < n이면서 nums[i]가 curr과 같다면 해당 값은 배열에 있는 것이므로 i와 curr을 각각 1씩 증가시킵니다.
값이 누락된 경우: 먼저 curr을 문자열로 변환해 temp에 저장한 뒤 curr을 1 증가시킵니다. 이후 상황은 세 가지로 나뉩니다.
- 바로 다음 값(nums[i])이 증가된 curr과 같다면 누락된 값이 하나뿐이므로 temp를 그대로 ret에 추가하고 다음 반복으로 넘어갑니다.
- 배열을 모두 순회한 상태(i == n)라면 남은 구간 전체가 누락된 것입니다. curr이 아직 upper 이하라면 temp에 "->"와 upper를 이어 붙여 마지막 구간을 완성하고, curr을 upper + 1로 만들어 반복을 종료합니다.
- 그 외의 경우(배열에 아직 값이 더 남아 있는 경우)에는 다음으로 존재하는 값 직전까지가 누락 구간이므로, temp에 "->"와 nums[i] - 1을 이어 붙여 구간을 완성한 뒤 curr을 nums[i]로 이동시킵니다.

4단계: 결과 반환

반복이 모두 끝나면 지금까지 누적한 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<string> findMissingRanges(vector<int>& t, int lower, int upper) {
      vector <int> nums;
      set <long long int> v;
      for(int i = 0; i < t.size(); i++){
         if(!v.count(t[i])){
            v.insert(t[i]);
            nums.push_back(t[i]);
         }
      }
      vector < string > ret;
      long long int curr = lower;
      int i = 0;
      int n = nums.size();
      while(curr <= upper){
         if(i < n && nums[i] == curr){
            i++;
            curr++;
         }
         else{
            string temp = to_string(curr);
            curr++;
            if(i < n && nums[i] == curr){
               ret.push_back(temp);
               continue;
            }
            else{
               if(i == n){
                  if(curr <= upper){
                     temp += "->";
                     temp += to_string(upper);
                     curr = (long long int )upper + 1;
                  }
                  ret.push_back(temp);
               }
               else{
                  temp += "->";
                  curr = nums[i];
                  temp += to_string(curr - 1);
                  curr = nums[i];
                  ret.push_back(temp);
               }
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,1,3,50,75};
   print_vector(ob.findMissingRanges(v, 0, 99));
}

실행 결과

입력

{0,1,3,50,75}, 0, 99

출력

[2, 4->49, 51->74, 76->99]

마무리

이 알고리즘은 배열을 한 번만 순회하며 누락 구간을 찾기 때문에 시간 복잡도는 O(n)입니다. 참고로 curr을 long long int로 선언한 이유는 upper가 INT_MAX일 때 curr + 1 연산에서 오버플로가 발생하는 것을 방지하기 위함입니다. 이러한 경계 조건 처리는 코딩 인터뷰에서 자주 확인되는 부분이므로 꼭 기억해 두시기 바랍니다.