C++로 서로 다른 N개의 정수 중 정확히 하나만 포함하는 최대 크기 구간 찾기

서로 다른 N개의 정수로 이루어진 배열이 있다고 가정해 봅시다. 이때 주어진 N개의 정수 중 정확히 하나만 포함하면서, 1 ≤ L ≤ R ≤ 10⁵ 조건을 만족하는 구간 [L, R] 중 길이가 가장 긴 구간을 찾아야 합니다.

예를 들어 배열이 Arr = [5, 10, 200]이라면 출력값은 99990입니다. 가능한 모든 구간은 [1, 9], [6, 199], [11, 100000]이며, 이 중 마지막 구간이 99990개의 정수를 포함하여 가장 깁니다.

접근 방법

핵심 아이디어는 간단합니다. 먼저 구간에 포함시킬 기준 원소를 하나 고정한 뒤, 다른 원소들과 겹치지 않는 범위 내에서 구간을 왼쪽과 오른쪽으로 얼마나 확장할 수 있는지 살펴보는 것입니다.

구체적인 절차는 다음과 같습니다.

알고리즘 단계

1. 배열을 오름차순으로 정렬합니다.
2. 경계 처리를 위해 배열 앞에 0, 뒤에 100001을 추가합니다.
3. 각 원소 i에 대해 이전 원소와 다음 원소를 이용해 구간의 시작(Left)과 끝(Right)을 결정합니다.
4. 첫 번째 원소와 마지막 원소처럼 경계에 있는 경우도 위 방식으로 자연스럽게 처리됩니다.
5. 모든 원소에 대해 계산한 구간 길이 중 최댓값을 반환합니다.

C++ 구현 예제

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int maximumSize(vector<int>& vec, int n) {
   vec.push_back(0);
   vec.push_back(100001);
   n += 2;
   sort(vec.begin(), vec.end());
   int max_value = 0;
   for (int i = 1; i < n - 1; i++) {
      int Left = vec[i - 1] + 1;
      int Right = vec[i + 1] - 1;
      int count = Right - Left + 1;
      max_value = max(max_value, count);
   }
   return max_value;
}
int main() {
   vector<int> v;
   v.push_back(200);
   v.push_back(10);
   v.push_back(5);
   int n = v.size();
   cout << "Maximum Size is: " << maximumSize(v, n);
}

실행 결과

Maximum Size is: 99990

복잡도 분석

정렬에 O(N log N)의 시간이 걸리고, 이후 각 원소를 한 번씩 순회하므로 전체 시간 복잡도는 O(N log N)입니다. 추가로 사용하는 공간은 상수 수준이므로 공간 복잡도는 O(1)입니다.