C++ 코딩 퍼즐: 뺄셈 없이 '나를 제외한 합' 배열 만들기

이번 글에서는 배열과 관련된 흥미로운 코딩 퍼즐을 살펴보겠습니다. n개의 요소를 가진 배열이 주어졌을 때, 같은 크기의 새로운 배열을 만들어야 합니다. 이때 결과 배열의 i번째 위치에는 원본 배열에서 i번째 요소를 제외한 나머지 모든 요소들의 합이 들어가야 합니다.

여기에 한 가지 까다로운 제약 조건이 있습니다. 바로 뺄셈 연산자를 사용할 수 없다는 점입니다.

왜 이 문제가 어려울까?

만약 뺄셈을 사용할 수 있다면 문제는 아주 간단합니다. 전체 요소의 합을 미리 구한 뒤, 각 위치에서 해당 요소만 빼주면 되기 때문입니다. 하지만 뺄셈이 금지되어 있으므로, 다른 방식으로 접근해야 합니다.

이 글에서 소개하는 방법은 직관적입니다. 인덱스 i가 0부터 n-1까지 순회할 때마다, 배열의 모든 요소를 다시 한번 순회하면서 i번째 요소만 건너뛰고 나머지를 모두 더하는 것입니다.

알고리즘

sumArray(arr, n)

begin
    define an array called res of size n
    for all elements i in arr, do
        sum := 0
        for all elements j in arr, do
            if i and j are not same, then
                sum := sum + arr[j]
            end if
        done
        res[i] = sum
    done
    return res
end

C++ 예제 코드

#include<iostream>
using namespace std;

void printArray(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void sumArray(int arr[], int resArr[], int n) {
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = 0; j < n; j++) {
            if(i != j) {
                sum += arr[j];
            }
        }
        resArr[i] = sum;
    }
}

main() {
    int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
    int resArr[7];
    cout << "Initial Array: ";
    printArray(myArr, 7);
    sumArray(myArr, resArr, 7);
    cout << "Final Array: ";
    printArray(resArr, 7);
}

실행 결과

Initial Array: 5 4 7 6 9 2 3
Final Array: 31 32 29 30 27 34 33

결과를 검증해 보면 규칙이 잘 맞습니다. 예를 들어 원본 배열의 총합은 36이고, 첫 번째 결과 값 31은 36에서 첫 요소 5를 제외한 값(4+7+6+9+2+3)과 정확히 일치합니다. 마찬가지로 두 번째 값 32는 5+7+6+9+2+3의 합입니다.

시간 복잡도 분석

이 방법은 이중 반복문을 사용하기 때문에 시간 복잡도는 O(n²)입니다. 뺄셈이 허용된다면 총합을 한 번만 구하고 각 요소를 빼는 방식으로 O(n)에 해결할 수 있지만, 이 퍼즐의 제약 조건 때문에 단순 누적 방식이 필요합니다. 배열의 크기가 작거나 중간 정도일 때는 충분히 실용적인 접근법입니다.