C++에서 범위의 모든 원소가 배열에 존재하도록 추가해야 할 원소 개수 구하기

이 문제에서는 n개의 숫자로 이루어진 배열 arr[]가 주어집니다. 목표는 배열의 최솟값부터 최댓값까지의 범위에 속한 모든 원소가 배열 안에 존재하도록 추가해야 할 원소의 개수를 구하는 프로그램을 작성하는 것입니다.

문제 설명

배열에는 여러 숫자가 들어 있지만, 최솟값과 최댓값 사이의 일부 숫자는 비어 있을 수 있습니다. 이때 범위를 연속적으로 완성하기 위해 몇 개의 숫자를 새로 추가해야 하는지 계산해야 합니다. 예를 들어 배열이 {1, 3}이라면 목표 범위는 1~3이고, 빠진 숫자 2 하나를 추가해야 하므로 정답은 1이 됩니다.

예제로 이해하기

입력: arr[] = {5, 8, 3, 1, 6, 2}
출력: 2

설명: 배열의 최솟값은 1, 최댓값은 8이므로 목표 범위는 1~8입니다. 현재 배열에 없는 숫자는 4와 7이며, 따라서 2개의 원소를 추가해야 합니다.

해결 접근 방법

가장 직관적인 방법은 배열을 먼저 오름차순으로 정렬한 뒤, 인접한 두 원소를 차례대로 비교하는 것입니다. 정렬된 상태에서 연속된 두 값의 차이가 1보다 크면 그 사이에 누락된 숫자가 존재한다는 뜻입니다. 이때 누락된 개수는 '다음 원소 값 − 현재 원소 값 − 1'이므로, 모든 간격에 대해 이 값을 누적하면 추가해야 할 전체 원소 개수를 구할 수 있습니다.

알고리즘

1단계: 배열을 오름차순으로 정렬합니다.
2단계: i를 0부터 n-2까지 반복합니다.
2-1단계: arr[i+1]과 arr[i]의 차이가 1보다 크면, count에 (arr[i+1] − arr[i] − 1)을 더합니다.
3단계: count를 반환합니다.

구현 예제 (C++)

#include <bits/stdc++.h>
using namespace std;

int calcEleRequired(int arr[], int n)
{
    int count = 0;
    sort(arr, arr + n);
    for (int i = 0; i < n - 1; i++)
        if (arr[i] + 1 != arr[i + 1])
            count += arr[i + 1] - arr[i] - 1; // 간격 사이의 누락 원소 수
    return count;
}

int main()
{
    int arr[] = { 5, 8, 3, 1, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "범위를 완성하기 위해 추가해야 할 원소의 개수: " << calcEleRequired(arr, n);
    return 0;
}

출력 결과

범위를 완성하기 위해 추가해야 할 원소의 개수: 2

복잡도 분석

시간 복잡도: 배열 정렬에 O(n log n)이 소요되며, 이후의 선형 탐색은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다.
공간 복잡도: 추가 메모리 없이 제자리 정렬을 사용하므로 O(1)입니다.

참고 사항

간격마다 count를 1씩만 증가시키는 방식은 {1, 8}처럼 한 번의 건너뜀에서 여러 숫자가 동시에 빠진 경우 정확한 답을 구할 수 없습니다. 반드시 (arr[i+1] − arr[i] − 1)을 더해야 실제 누락된 원소 수를 올바르게 계산할 수 있습니다.