문제 소개
배열과 관련된 흥미로운 문제를 하나 살펴보겠습니다. n개의 원소를 가진 배열이 주어졌을 때, 같은 크기의 또 다른 배열을 만들어야 합니다. 이때 결과 배열의 i번째 위치에는 원본 배열에서 i번째 원소를 제외한 나머지 모든 원소들의 곱이 들어가야 합니다.
여기서 중요한 제약 조건은 바로 나눗셈 연산자(/)를 사용할 수 없다는 점입니다.
나눗셈을 쓸 수 있다면 얼마나 쉬울까?
만약 나눗셈 사용이 허용된다면 문제는 매우 간단해집니다. 먼저 배열의 모든 원소를 곱해 전체 곱을 구한 뒤, i번째 원소로 나누어 그 값을 결과 배열의 i번째 위치에 저장하면 끝입니다.
하지만 나눗셈 없이 풀어야 하므로 다른 방법이 필요합니다.
접근 방법: 왼쪽·오른쪽 누적 곱 배열
핵심 아이디어는 두 개의 보조 배열을 만드는 것입니다.
- left[i] : arr[i] 자신을 제외하고, 그 왼쪽에 있는 모든 원소들의 곱
- right[i] : arr[i] 자신을 제외하고, 그 오른쪽에 있는 모든 원소들의 곱
두 배열이 준비되면 최종 결과는 아래처럼 간단히 계산됩니다.
res[i] = left[i] * right[i]
이 방법은 O(n) 시간 안에 동작하지만, 보조 배열 두 개를 위한 추가 공간(O(n))이 필요하다는 점에 유의해야 합니다.
알고리즘
productArray(arr, n)
begin
크기가 n인 두 배열 left와 right 선언
크기가 n인 배열 res 선언
left의 첫 번째 원소와 right의 마지막 원소를 1로 설정
i를 1부터 n까지 반복:
left[i] = left[i-1] * arr[i-1]
i를 n-1부터 1까지 감소시키며 반복:
right[i] = right[i+1] * arr[i+1]
i를 1부터 n까지 반복:
res[i] = left[i] * right[i]
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) {
//left, right 배열 생성
int *left = new int[sizeof(int)*n];
int *right = new int[sizeof(int)*n];
//left[]의 첫 원소와 right[]의 마지막 원소를 1로 설정
left[0] = right[n-1] = 1;
for(int i = 1; i<n; i++) {
left[i] = left[i-1] * arr[i-1];
}
for(int i = n-2; i>=0; i--) {
right[i] = right[i+1] * arr[i+1];
}
//left와 right 배열을 이용해 곱 배열 계산
for(int i = 0; i<n; i++) {
product[i] = left[i] * right[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);
}
실행 결과
Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120
결과 검증
예를 들어 첫 번째 결과 값 9072는 5를 제외한 나머지 원소들의 곱입니다.
4 × 7 × 6 × 9 × 2 × 3 = 9072
같은 방식으로 두 번째 값 11340은 4를 제외한 5 × 7 × 6 × 9 × 2 × 3의 곱이며, 나머지 위치도 동일한 규칙으로 계산됩니다.
복잡도 분석
- 시간 복잡도 : O(n) — 배열을 세 번 순회하므로 전체적으로 선형 시간이 걸립니다.
- 공간 복잡도 : O(n) — left, right 두 개의 보조 배열을 위해 추가 메모리가 필요합니다.
마무리
이처럼 나눗셈 연산 없이도 '왼쪽 누적 곱'과 '오른쪽 누적 곱'이라는 개념을 활용하면 각 원소를 제외한 전체 곱을 효율적으로 구할 수 있습니다. 이 기법은 코딩 인터뷰에서 자주 등장하는 대표적인 배열 문제이므로, 누적 곱(Prefix/Suffix Product) 패턴으로 익혀두면 다양한 변형 문제에도 유용하게 적용할 수 있습니다.