C++로 암호화된 배열(자기 자신을 제외한 요소들의 합)에서 원본 배열 복원하기

정수로 이루어진 암호화된 배열이 하나 주어져 있다고 가정해 보겠습니다. 예를 들어 암호화된 배열이 A = [10, 14, 12, 13, 11]이고, 원본 배열이 B = [5, 1, 3, 2, 4]라고 합시다. 이때 암호화 배열의 각 인덱스 i에 해당하는 값은 다음 규칙을 따릅니다.

A[i] = 원본 배열 B에서 i번째 요소를 제외한 나머지 모든 요소의 합 (단, i ≠ j인 모든 j에 대해 B[j]의 합)

즉, 각 위치의 값은 자기 자신을 빼고 계산된 합이므로, 우리의 목표는 이 암호화된 배열만 보고 원본 배열을 되찾아내는 것입니다.

핵심 아이디어: 산술적 관찰

이 문제는 단순한 수학적 관찰만으로 해결할 수 있습니다. 배열의 크기가 n이라고 할 때, 이해를 돕기 위해 크기가 4인 경우를 생각해 봅시다. 원본 배열을 B = [a, b, c, d]라 하면, 암호화된 배열 A는 다음과 같이 구성됩니다.

A = [b+c+d, a+c+d, a+b+d, a+b+c]

여기서 A의 모든 요소를 더하면 어떻게 될까요?

sum = (b+c+d) + (a+c+d) + (a+b+d) + (a+b+c) = 3 × (a+b+c+d)

각 원소가 자신을 제외한 나머지 (n−1)개의 합에 정확히 한 번씩 포함되므로, A의 총합은 (n−1) × B의 총합이 됩니다. 따라서 원본 배열의 총합은 다음과 같이 구할 수 있습니다.

B의 총합 = A의 총합 / (n−1)

총합을 알게 되면 각 원소는 아주 간단하게 복원됩니다.

B[i] = 총합 − A[i]

C++ 구현 예제

#include <iostream>
using namespace std;

void showOriginalArray(int arr[], int n) {
    int sum = 0;
    // 암호화 배열의 전체 합 계산
    for (int i = 0; i < n; i++)
        sum += arr[i];
    // 원본 배열의 총합 = 전체 합 / (n - 1)
    sum = sum / (n - 1);
    // 각 원소 = 총합 - 현재 암호화 값
    for (int i = 0; i < n; i++)
        cout << (sum - arr[i]) << " ";
}

int main() {
    int arr[] = {10, 14, 12, 13, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    showOriginalArray(arr, n);
    return 0;
}

실행 결과

5 1 3 2 4

복잡도 분석

이 알고리즘은 배열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가적인 공간 없이 결과를 바로 출력하므로 공간 복잡도는 O(1)입니다. 매우 효율적인 해결 방식이라 할 수 있습니다.