.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
•
주의
나눗셈을 하지 않고 O(n)에 풀이하라.
My solution
[1, 2, 3, 4]가 입력되면 [24, 12, 8, 6]으로 각각의 원래 인덱스에 곱이 들어온다.
주의사항을 보면 나눗셈을 하지말라고 한다.
가장 쉽게 생각해볼 수 있는 풀이는 for문으로 모든 배열의 원소를 곱하고 for문을 돌면서 그 곱에 각 원소를 나눈 다음 배열에 저장하는 방식이다.
이 방식은 나눗셈이 필요한데 이 방식으로 하지 말라는 의미다.
방문하는 원소를 기준으로 좌, 우의 합을 더해주는 방식으로 해야한다고 생각했었다.
O(n)이라고 하면 투 포인터로 풀어야된다고 추측했다. 정확한 풀이 로직은 정해져있는 것 같다.
왼쪽부터 곱셈값을 left 배열에 넣는다.
오른쪽부터 곱셈값은 right배열에 넣는다.
들어가는 곱셈값은 왼쪽(오른쪽)부터 현재 원소까지의 곱이다.
기본 곱셈값은 1부터 시작한다.
이렇게 left 배열은 [1,1,2,6]이 되고 right 배열은 [24,12,4,1]이 된다.
두 배열은 for문을 돌면서 같은 인덱스의 값을 곱해서 result 배열에 넣는다.
추측한 것과 다르게 2개의 배열을 가지고 양쪽에서 곱셈을 진행한 곱셈값들을 가지고 마지막에 둘을 이용해서 결과 배열을 만드는 방식이었다.
Code
const productOfArrayExceptSelf = function (arr) {
const result = [];
const left = [];
const right = [];
let leftProduct = 1;
let rightProduct = 1;
const len = arr.length;
for (let i = 0; i < len; i++) {
left[i] = leftProduct;
leftProduct *= arr[i];
right[len - i - 1] = rightProduct;
rightProduct *= arr[len - i - 1];
}
for (let i = 0; i < len; i++) {
result[i] = left[i] * right[i];
}
return result;
};
JavaScript
복사
Solution
1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
풀이방식을 한정하게 했으므로 이 방식을 유도한 것이다.
하지만 공간 복잡도를 좀더 낮출 수 있다. 마지막 값 곱셈은 제외하고 결과 [1, 1, 2, 6]을 구현해보면
p = 1;
for(let i = 0; i < arr.length; i++){
result.push(p);
p = p * arr[i];
}
JavaScript
복사
이때 right 배열을 만들지 않고 재활용하는 방식을 사용한다.(출력에 필요한 공간은 공간복잡도에 포함하지 않고 O(1)으로 줄이기 위함)
right 배열에 넣어야할 값은 p에 유지하면서 바로 계산해서 result에 넣는다.(p는 1부터 시작)
const productOfArrayExceptSelf = function (arr) {
const result = [];
const len = arr.length;
let p = 1;
for (let i = 0; i < len; i++) {
result.push(p);
p *= arr[i];
}
p = 1;
for (let i = len - 1; i >= 0; i--) {
result[i] *= p;
p *= arr[i];
}
return result;
};
JavaScript
복사
