이 글에서는 배열과 관련된 흥미로운 문제인 곱 배열(Product Array) 퍼즐을 다뤄보겠습니다. n개의 원소를 가진 배열이 주어졌을 때, 같은 크기의 새로운 배열을 만들어야 합니다. 이때 새 배열의 i번째 위치에는 원본 배열의 i번째 원소를 제외한 나머지 모든 원소들의 곱이 들어가야 합니다.
여기에는 두 가지 까다로운 제약 조건이 있습니다. 첫째, 나눗셈 연산자를 사용할 수 없습니다. 둘째, O(1)의 추가 공간, 즉 별도의 보조 배열 없이 문제를 해결해야 합니다.
나눗셈을 쓰면 얼마나 쉬워지나?
만약 나눗셈을 사용할 수 있다면 문제는 매우 간단합니다. 배열 전체 원소의 곱 P를 미리 구해 놓은 뒤, 결과 배열의 i번째 값을 P ÷ arr[i]로 채워주기만 하면 되기 때문입니다. 하지만 이 문제에서는 나눗셈이 금지되어 있으므로 다른 접근 방식이 필요합니다.
핵심 아이디어: 왼쪽 곱 × 오른쪽 곱
나눗셈 없이 O(1) 공간으로 문제를 해결하는 핵심은 임시 변수(temp) 하나를 활용하는 것입니다. 각 인덱스 i를 기준으로 다음 두 값을 차례로 계산합니다.
- 왼쪽 부분의 곱: arr[0]부터 arr[i-1]까지의 곱
- 오른쪽 부분의 곱: arr[i+1]부터 arr[n-1]까지의 곱
첫 번째 순회에서 각 위치에 자기 자신을 제외한 왼쪽 원소들의 곱을 저장하고, 두 번째 순회(오른쪽에서 왼쪽으로)에서 오른쪽 곱을 곱해주면 최종 결과가 완성됩니다. 이 방식은 결과 배열 하나만 사용하므로 입력·출력 외에는 추가 공간이 전혀 필요하지 않습니다.
알고리즘
productArray(arr, n)
begin
define an array called res of size n
fill the res array with 1
temp := 1
for i in range 0 to n-1, do
res[i] := temp
temp := temp * arr[i]
done
temp := 1
for i in range n-1 down to 0, do
res[i] := res[i] * temp
temp := temp * arr[i]
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 productArray(int arr[], int product[], int n) {
int temp = 1;
// product 배열을 1로 초기화
for(int i = 0; i < n; i++) {
product[i] = 1;
}
// temp에는 arr[i]를 제외한 왼쪽 원소들의 곱이 담김
for(int i = 0; i < n; i++) {
product[i] = temp;
temp *= arr[i];
}
temp = 1;
// temp에는 arr[i]를 제외한 오른쪽 원소들의 곱이 담김
for(int i = n - 1; i >= 0; i--) {
product[i] *= temp;
temp *= arr[i];
}
}
int main() {
int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
int resArr[7];
cout << "Initial Array: ";
printArray(myArr, 7);
productArray(myArr, resArr, 7);
cout << "Final Array: ";
printArray(resArr, 7);
return 0;
}
실행 결과
Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120
동작 과정 살펴보기
입력 배열이 [5, 4, 7, 6, 9, 2, 3]일 때의 동작을 단계별로 확인해 보겠습니다.
- 왼쪽 순회 후: product 배열에는 [1, 5, 20, 140, 840, 7560, 15120]이 저장됩니다. 각 값은 해당 위치 왼쪽에 있는 원소들의 곱입니다.
- 오른쪽 순회 후: 여기에 오른쪽 원소들의 곱을 곱하면 [9072, 11340, 6480, 7560, 5040, 22680, 15120]이라는 최종 결과가 나옵니다.
예를 들어 세 번째 위치(값 7)의 결과인 6480은 5 × 4 × 6 × 9 × 2 × 3, 즉 7을 제외한 나머지 원소들의 곱과 정확히 일치합니다.
복잡도 분석
- 시간 복잡도: 배열을 두 번 순회하므로 O(n)
- 공간 복잡도: 임시 변수 하나만 사용하므로 O(1)
이처럼 나눗셈 연산 없이도 선형 시간 안에 문제를 해결할 수 있으며, 추가 메모리 사용을 상수 수준으로 유지할 수 있습니다. 이 기법은 면접에서 자주 등장하는 대표적인 배열 문제이므로 왼쪽 곱·오른쪽 곱 누적 방식을 꼭 익혀두시기 바랍니다.