C++에서 정렬된 두 배열 사이의 추가 요소 인덱스 찾기

이 글에서는 크기가 각각 n과 n+1로 주어진 두 개의 정렬된 배열 arr1과 arr2에서 추가 요소(extra element)의 인덱스를 찾는 방법을 다룹니다. 두 배열은 단 하나의 요소를 제외하면 모든 값이 동일합니다.

문제 설명

크기가 n+1인 배열에는 존재하지만 크기가 n인 배열에는 포함되어 있지 않은 요소의 위치(인덱스)를 찾아야 합니다.

예시로 문제 이해하기

입력:
arr1[n] = {3, 5, 7, 8, 9, 12}
arr2[n+1] = {3, 4, 5, 7, 8, 9, 12}

출력: 1

설명: 값이 4인 요소가 바로 추가된 요소이며, arr2에서 인덱스 1에 위치합니다.

방법 1 – 선형 탐색

가장 간단한 해결 방법은 두 배열이 모두 정렬되어 있다는 점을 활용하는 것입니다. 배열의 앞부분부터 순서대로 요소를 비교하는 선형 탐색(linear search)을 수행하면, 처음으로 값이 일치하지 않는 지점이 곧 arr2에만 존재하는 추가 요소의 위치입니다.

알고리즘

1단계: i를 0부터 n-1까지 반복합니다.

1-1단계: arr1[i] != arr2[i]인 경우(값이 다른 요소 발견), 반복문을 종료합니다.

2단계: 현재 i 값을 반환합니다.

이 방법의 시간 복잡도는 O(n)입니다.

구현 예제

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
    int i;
    for (i = 0; i < n; i++)
        if (arr1[i] != arr2[i])
            break;
    return i;
}

int main()
{
    int arr1[] = {3, 5, 7, 8, 9, 12};
    int arr2[] = {3, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int extraIndex = findExtraElement(arr1, arr2, n);
    cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
    return 0;
}

실행 결과

The extra element is at index (1) and the value is 4

방법 2 – 이진 탐색으로 성능 개선

배열이 정렬되어 있다는 조건을 더 적극적으로 활용하면, 선형 탐색 대신 이진 탐색(binary search)을 적용해 알고리즘의 연산 시간을 크게 줄일 수 있습니다. 가운데(mid) 위치에서 두 배열의 값이 같다면 추가 요소는 그보다 뒤쪽에 있고, 값이 다르다면 현재 위치 또는 그 앞쪽에 있다는 원리를 이용합니다. 시간 복잡도는 O(log n)으로, 배열의 크기가 클수록 선형 탐색보다 훨씬 유리합니다.

구현 예제

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {

    int extraIndex = n;
    int start = 0, end = n - 1;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (arr2[mid] == arr1[mid])
            start = mid + 1;
        else
        {
            extraIndex = mid;
            end = mid - 1;
        }
    }
    return extraIndex;
}

int main()
{
    int arr1[] = {3, 5, 7, 8, 9, 12};
    int arr2[] = {3, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int extraIndex = findExtraElement(arr1, arr2, n);
    cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
    return 0;
}

실행 결과

The extra element is at index (1) and the value is 4

방법 3 – 배열 합의 차이 활용

또 다른 접근 방식은 두 배열의 합을 각각 계산한 뒤 그 차이를 구하는 것입니다. 두 배열은 한 요소를 제외하고 모두 같으므로, 합의 차이가 곧 추가 요소의 값이 됩니다. 이후 이 값을 크기가 n+1인 배열(arr2)에서 검색하여 해당 인덱스를 찾으면 됩니다.

구현 예제

#include <iostream>
using namespace std;

int calcArraysum(int arr[], int n){
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += arr[i];
    return sum;
}

int findExtraElement(int arr1[], int arr2[], int n) {

    int extraValue = calcArraysum(arr2, n+1) - calcArraysum(arr1, n);

    for (int i = 0; i < n; i++)
    {
        if (arr2[i] == extraValue)
            return i;
    }
    return -1;
}

int main()
{
    int arr1[] = {3, 5, 7, 8, 9, 12};
    int arr2[] = {3, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int extraIndex = findExtraElement(arr1, arr2, n);
    cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
    return 0;
}

실행 결과

The extra element is at index (1) and the value is 4

마무리

세 가지 방법 모두 올바른 결과를 얻을 수 있습니다. 하지만 배열의 크기가 커질수록 O(log n)의 이진 탐색 방법이 가장 효율적이며, 선형 탐색과 합 차이 방식은 O(n)의 시간 복잡도를 가집니다. 참고로 합 차이 방식은 배열 요소의 합이 매우 클 경우 정수 오버플로가 발생할 수 있으므로, 자료형 선택에 주의해야 합니다.