C++ 두 개의 방정식으로 반복 숫자와 누락된 숫자 찾기

문제 소개

크기가 N인 배열 arr[]이 주어집니다. 배열에는 1부터 N까지의 정수가 담겨 있지만, 그중 한 숫자 x는 빠져 있고(누락), 대신 다른 숫자 y 하나가 두 번 등장합니다(반복). 이 글에서는 두 개의 방정식을 활용해 반복되는 숫자와 누락된 숫자를 찾는 방법을 알아보겠습니다.

예제를 통해 문제를 살펴보겠습니다.

입력

arr[] = {1, 2, 3, 3}

출력

누락된 숫자 = 4, 반복 숫자 = 3

해결 접근 방식: 두 개의 방정식 세우기

핵심 아이디어는 간단합니다. 누락된 값 x와 반복 값 y에 관한 두 개의 방정식을 만든 뒤, 이를 연립해 풀면 됩니다.

첫 번째 방정식: 합 이용하기

배열 원소 전체의 합(arrSum)은 '1부터 N까지 자연수의 합'에서 누락된 x가 빠지고, 대신 y가 한 번 더 포함된 값입니다.

arrSum = Sum(N) - x + y
y - x = arrSum - Sum(N)

이것이 첫 번째 방정식입니다.

두 번째 방정식: 제곱합 이용하기

같은 논리를 제곱합에 적용하면 다음과 같습니다.

arrSumsq = sqSum(N) - x2 + y2
(y - x)(y + x) = arrSumsq - sqSum(N)

여기에 첫 번째 방정식에서 구한 (y - x) 값을 대입하면,

x + y = (arrSumsq - sqSum(N)) / (arrSum - Sum(N))

x와 y 구하기

이제 두 식을 더하거나 빼면 각각 y와 x를 구할 수 있습니다.

y = { (arrSumsq - sqSum(N)) / (arrSum - Sum(N)) + (arrSum - Sum(N)) } / 2
x = y - (arrSum - Sum(N))

참고로 1부터 N까지의 합과 제곱합은 다음 공식으로 바로 계산할 수 있습니다.

Sum(N) = N × (N + 1) / 2
sqSum(N) = N × (N + 1) × (2N + 1) / 6

여기서 arrSum은 배열 모든 원소의 합, arrSumsq는 배열 모든 원소 제곱의 합입니다.

C++ 구현 예제

다음 프로그램은 위 접근 방식이 실제로 동작하는 모습을 보여줍니다.

#include <iostream>
using namespace std;

void findMissingAndRepeatingVal(int arr[], int n) {
    // 오버플로 방지를 위해 long long 사용
    long long sumN = (long long)n * (n + 1) / 2;
    long long sqSumN = (long long)n * (n + 1) * (2 * n + 1) / 6;

    long long arrSum = 0, arrSqSum = 0;
    for (int i = 0; i < n; i++) {
        arrSum += arr[i];
        arrSqSum += (long long)arr[i] * arr[i];
    }

    long long diff = arrSum - sumN;               // y - x
    long long sumXY = (arrSqSum - sqSumN) / diff; // y + x

    long long y = (diff + sumXY) / 2;  // 반복 숫자
    long long x = y - diff;            // 누락된 숫자

    cout << "배열에서 누락된 값: " << x << endl;
    cout << "배열에서 두 번 나타나는 값: " << y << endl;
}

int main() {
    int arr[] = { 1, 2, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findMissingAndRepeatingVal(arr, n);
    return 0;
}

출력 결과

배열에서 누락된 값: 5
배열에서 두 번 나타나는 값: 2

배열 {1, 2, 2, 3, 4}에는 1부터 5까지의 숫자 중 5가 빠져 있고, 2가 두 번 등장하므로 올바른 결과입니다.

복잡도 분석

시간 복잡도: O(N) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 입력 크기와 무관한 상수 공간만 사용합니다.

마무리

합과 제곱합이라는 두 개의 방정식만 세우면, 별도의 추가 배열이나 정렬 없이도 반복 숫자와 누락된 숫자를 선형 시간에 구할 수 있습니다. 다만 N이 매우 클 경우 합의 값이 커질 수 있으므로, 위 예제처럼 long long 같은 넉넉한 자료형을 사용하는 것이 안전합니다.