C 언어로 풀어보는 곱 배열 퍼즐: 나눗셈 없이 자기 자신을 제외한 곱 구하기

배열(array)은 동일한 데이터 타입의 요소들을 담는 컨테이너입니다. 곱 배열 퍼즐(Product Array Puzzle)은 배열에 담긴 모든 요소들의 곱을 다루는 대표적인 알고리즘 문제로, 코딩 인터뷰에서도 자주 등장합니다.

문제 정의

곱 배열 퍼즐의 목표는 배열의 각 위치에 대해 자기 자신을 제외한 나머지 모든 요소들의 곱을 구하는 것입니다. 단, 다음과 같은 제약 조건이 주어집니다.

• 나눗셈 연산자(/)를 사용할 수 없습니다.
• 결괏값은 반드시 별도의 배열에 저장해야 합니다.

전체 요소의 곱을 먼저 구한 뒤 각 요소로 나누면 간단히 해결되지만, 나눗셈이 금지되어 있으므로 다른 접근 방식이 필요합니다.

해결 전략: 왼쪽 곱과 오른쪽 곱

핵심 아이디어는 각 인덱스를 기준으로 왼쪽 요소들의 누적 곱(left)과 오른쪽 요소들의 누적 곱(right)을 미리 계산해 두고, 이 둘을 곱하여 최종 결과를 만드는 것입니다.

1. left[i] — 인덱스 i보다 왼쪽에 있는 모든 요소들의 곱
2. right[i] — 인덱스 i보다 오른쪽에 있는 모든 요소들의 곱
3. prod[i] = left[i] × right[i] — 자기 자신을 제외한 전체 곱

이 방법을 사용하면 나눗셈 없이도 시간 복잡도 O(n), 공간 복잡도 O(n)으로 문제를 해결할 수 있습니다.

C 언어 구현 예제

#include<stdio.h>
#include<stdlib.h>
void productfind(int arr[], int n) {
    int *left = (int *)malloc(sizeof(int)*n);
    int *right = (int *)malloc(sizeof(int)*n);
    int *prod = (int *)malloc(sizeof(int)*n);
    int i, j;
    left[0] = 1;
    right[n-1] = 1;
    for(i = 1; i < n; i++)
        left[i] = arr[i-1] * left[i-1];
    for(j = n-2; j >= 0; j--)
        right[j] = arr[j+1] * right[j+1];
    for (i = 0; i < n; i++)
        prod[i] = left[i] * right[i];
    for (i = 0; i < n; i++)
        printf("%d ", prod[i]);
    return;
}
int main() {
    int arr[] = {10, 3, 5, 6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("The array is : \n");
    for(int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
    printf("\nThe product array is: \n");
    productfind(arr, n);
}

실행 결과

The array is :
10 3 5 6 2
The product array is:
180 600 360 300 900

동작 원리 상세 분석

예제 배열 {10, 3, 5, 6, 2}를 기준으로 각 단계의 계산 결과를 정리하면 다음과 같습니다.

예를 들어 인덱스 2(값 5)의 경우, 왼쪽 요소들의 곱은 10×3=30이고 오른쪽 요소들의 곱은 6×2=12이므로 최종 결과는 30×12=360이 됩니다. 이처럼 각 위치에서 자기 자신을 제외한 모든 요소의 곱이 정확히 계산됩니다.

복잡도 분석

• 시간 복잡도: O(n) — 배열을 여러 번 순회하지만 모두 선형 시간 안에 처리됩니다.
• 공간 복잡도: O(n) — left, right, prod 세 개의 보조 배열이 필요합니다.

참고로 메모리 사용량을 줄이고 싶다면 출력 배열 하나에 왼쪽 누적 곱을 저장한 뒤, 오른쪽 곱은 변수 하나로 누적하면서 곱해 주는 방식으로 보조 공간을 O(1)(출력 배열 제외)까지 줄일 수도 있습니다.