[Question] 12. 각 원소가 자신을 제외한 나머지 원소들의 곱셈하기

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다.

정수로된 배열이 주어지면, 각 원소가 자기 자신을 제외한 나머지 원소들의 곱셈이 되게하라.

단, 나누기 사용 금지, 시간 복잡도 0(n)

예제 }

Input : [1, 2, 3, 4, 5]

Output : [120, 60, 40, 30, 24]

여기서 중요한 것은 나누기 사용이 안된다는 것과 O(n) 시간 복잡도여야 한다는 것이다.

여기 input 예제를 보면

Input a = [a[0], a[1], a[2], a[3], a[4]]
output =
[
a[1]*a[2]*a[3]*a[4],
a[0]*a[2]*a[3]*a[4],
a[0]*a[1]*a[3]*a[4],
a[0]*a[1]*a[2]*a[4],
a[0]*a[1]*a[2]*a[3]
]

그럼 여기서 두 개의 배열을 만들어준다. O(n)*2 = O(n)

int one[N]; int product = 1;
for(int i = 0; i < N; i++) {
    one[i] = product;
    product *= input[i]; 
}
int two[N]; int product = 1;
for(int i = N-1; i >= 0; i--) {
    two[i] = product;
    product *= input[i];
}

int[] one = [ 
1, 
a[0], 
a[0]*a[1], 
a[0]*a[1]*a[2], 
a[0]*a[1]*a[2]*a[3]
]
int[] two = [
a[1]*a[2]*a[3]*a[4], 
a[2]*a[3]*a[4], 
a[3]*a[4],
a[4],
1
]
int[] output = [
a[1]*a[2]*a[3]*a[4], 
a[0]*a[2]*a[3]*a[4], 
a[0]*a[1]*a[3]*a[4],
a[0]*a[1]*a[2]*a[4],
a[0]*a[1]*a[2]*a[3]
]

array one 과 array two 의 각 원소들을 서로 곱해주면 array output 이 나온다.

int output[N]
for(int i = 0; i < N; i++) {
    output[i] = one[i]*two[i];
}

총 시간 복잡도 = O(n) + O(n) + O(n) = O(3n) = O(n)