C++로 배열에서 누락된 짝수와 홀수 찾기

문제 정의

두 개의 정수 배열 even[]과 odd[]가 주어집니다. 각 배열은 연속된 짝수와 홀수 요소를 담고 있지만, 각 배열마다 하나의 요소가 누락되어 있습니다. 이 문제의 목표는 각 배열에서 누락된 숫자를 찾아내는 것입니다.

예시

even[] = {10, 8, 6, 16, 12}
odd[] = {3, 9, 13, 7, 11} 인 경우,
짝수 배열에서 누락된 숫자는 14이고,
홀수 배열에서 누락된 숫자는 5입니다.

접근 방식 (알고리즘)

배열 전체를 정렬하거나 탐색하는 대신, 등차수열의 합 공식을 활용하면 O(N) 시간 안에 효율적으로 해결할 수 있습니다.

• even[] 배열을 한 번 순회하며 최솟값(minEven), 최댓값(maxEven), 그리고 배열 원소들의 합(sumEvenArr)을 구합니다.
• 처음 N개 짝수의 합은 N × (N + 1)이라는 공식을 사용합니다. 2부터 minEven까지의 짝수 합을 sum1, 2부터 maxEven까지의 짝수 합을 sum2로 계산합니다.
• 짝수 배열이 완전했을 때의 기대 합은 reqSum = sum2 − sum1 + minEven입니다. 여기서 실제 배열의 합을 빼면 누락된 짝수를 구할 수 있습니다.
• 홀수도 같은 원리로 처리합니다. 처음 N개 홀수의 합은 N²이라는 공식을 이용해 기대 합을 구한 뒤, 실제 합을 빼면 누락된 홀수를 얻을 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
void findMissingNums(int even[], int sizeEven, int odd[], int sizeOdd) {
    int minEven = INT_MAX;
    int maxEven = INT_MIN;
    int minOdd = INT_MAX;
    int maxOdd = INT_MIN;
    int sumEvenArr = 0, sumOddArr = 0;
    for (int i = 0; i < sizeEven; i++) {
        minEven = min(minEven, even[i]);
        maxEven = max(maxEven, even[i]);
        sumEvenArr += even[i];
    }
    for (int i = 0; i < sizeOdd; i++) {
        minOdd = min(minOdd, odd[i]);
        maxOdd = max(maxOdd, odd[i]);
        sumOddArr += odd[i];
    }
    int totalTerms = 0, reqSum = 0;
    totalTerms = minEven / 2;
    int evenSumMin = totalTerms * (totalTerms + 1);
    totalTerms = maxEven / 2;
    int evenSumMax = totalTerms * (totalTerms + 1);
    reqSum = evenSumMax - evenSumMin + minEven;
    cout << "Missing even number = " << reqSum - sumEvenArr << "\n";
    totalTerms = (minOdd / 2) + 1;
    int oddSumMin = totalTerms * totalTerms;
    totalTerms = (maxOdd / 2) + 1;
    int oddSumMax = totalTerms * totalTerms;
    reqSum = oddSumMax - oddSumMin + minOdd;
    cout << "Missing odd number = " << reqSum - sumOddArr << "\n";
}
int main() {
    int even[] = {10, 8, 6, 16, 12};
    int sizeEven = sizeof(even) / sizeof(even[0]);
    int odd[] = {3, 9, 13, 7, 11};
    int sizeOdd = sizeof(odd) / sizeof(odd[0]);
    findMissingNums(even, sizeEven, odd, sizeOdd);
    return 0;
}

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

실행 결과

Missing even number = 14
Missing odd number = 5

정리

이 방법은 배열을 정렬하지 않고도 단 한 번의 순회(O(N))로 누락된 값을 찾을 수 있다는 점에서 매우 효율적입니다. 다만 배열의 크기가 매우 커질 경우 합계 값이 정수 범위를 초과할 수 있으므로, 필요하다면 long long 자료형을 사용하는 것이 안전합니다.