C++로 요소 하나 추가하기: 주어진 배열을 등차수열로 변환하는 방법

이번 튜토리얼에서는 요소를 딱 하나만 추가하여 주어진 배열을 등차수열(Arithmetic Progression, AP)로 변환하는 프로그램을 C++ 코드와 함께 살펴보겠습니다.

문제 개요

정수 배열이 하나 주어집니다. 우리의 과제는 이 배열에 단 하나의 요소를 추가하여 배열 전체가 등차수열을 이루도록 만들고, 그때 추가한 값을 반환하는 것입니다. 만약 어떤 방식으로도 등차수열을 만들 수 없다면 -1을 반환해야 합니다.

접근 방법

이 문제는 다음과 같은 논리로 해결할 수 있습니다.

배열을 먼저 오름차순으로 정렬합니다.
첫 두 요소의 차이를 공차(common difference) d로 가정합니다.
배열을 순회하며 인접한 두 요소의 차이가 d와 일치하지 않는 지점을 찾습니다.
차이가 정확히 2 * d라면 그 사이에 요소 하나를 끼워 넣으면 되므로, arr[i] - d를 추가할 값으로 기록합니다.
이미 요소를 한 번 추가한 상태에서 또 다른 불일치가 발견되거나, 차이가 2 * d가 아니라면 등차수열을 만드는 것이 불가능하므로 -1을 반환합니다.
순회가 끝날 때까지 추가할 요소가 없었다면, 배열 뒤에 이어붙일 값 즉 마지막 요소 + 공차(arr[n-1] + d)를 반환합니다.

C++ 구현 예시

#include<bits/stdc++.h>
using namespace std;
// 추가해야 할 숫자를 반환하는 함수
int print_number(int arr[], int n){
    sort(arr,arr+n);
    int d = arr[1] - arr[0];
    int numToAdd = -1;
    bool numAdded = false;
    for (int i = 2; i < n; i++) {
        int diff = arr[i] - arr[i - 1];
        if (diff != d) {
            if (numAdded)
                return -1;
            if (diff == 2 * d) {
                numToAdd = arr[i] - d;
                // 숫자가 추가된 경우
                numAdded = true;
            }
            // 불가능한 경우
            else
            return -1;
        }
    }
    // 마지막 요소 + 공차를 반환
    if (numToAdd == -1)
        return (arr[n - 1] + d);
    // 그렇지 않으면 선택된 숫자를 반환
    return numToAdd;
}
int main() {
    int arr[] = { 1, 3, 5, 7, 11, 13, 15 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << print_number(arr, n);
}

실행 결과

위 예제에서 입력 배열은 {1, 3, 5, 7, 11, 13, 15}입니다. 7과 11 사이에 9를 추가하면 공차가 2인 완전한 등차수열이 되므로, 프로그램은 9를 출력합니다.

시간 복잡도

배열 정렬에 O(n log n), 이후 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 추가 공간은 상수 수준으로 매우 효율적인 알고리즘입니다.