nums 배열 원소의 모두 곱한 값에서 해당 원소를 나눈 값을 출력하는 문제이다. 문제에서는 나눗셈하면 안 된다고 명시하고 있으므로 나눗셈하지 않고 풀어야 하는 게 포인트이다.
- 나눗셈을 하지 않아야 함.
- T=O(n), S=O(1)으로 풀어본다.
따라서 위의 두 가지를 목표로 이 문제를 해결해 보려고 한다.
Ideation
nums = [1, 2, 3, 4]의 경우를 살펴보자.
기대하는 정답은 [24, 12, 8, 6]이다. 해당 배열이 나오기 위해서는 전체 값의 곱(1*2*3*4 = 24)에 각자의 원소를 나누면 된다.
전체 곱에서 자신을 나누어 나오는 값은 자신을 제외한 모든 값의 곱과 동일하다.
e.g. 원소 3을 기준으로 한다면
1*2*3*4 / 3===1*2*4이다.
따라서 우리는 자신을 제외한 곱들의 왼쪽과 오른쪽을 곱해주면 정답이 된다는 것을 알 수 있다.
e.g. 원소 3을 기준으로 3의 좌/우의 곱은
1*2*4=8이다.
그러므로 왼쪽의 곱들과 오른쪽의 곱들을 기억해 두고 각 원소별 값을 출력해 주면 해결할 수 있다.
해당 원소까지의 왼쪽, 오른쪽 곱셈 값은 누적 배열을 활용하면 된다.
e.g. 원소 n 기준 왼쪽
[n-2, n-2 * n-1]*[n+1, n+1 * n+2]오른쪽
const nums = [1, 2, 3, 4];
// @NOTE: 요소의 왼쪽까지의 곱을 기준으로 하기 때문에 첫 번째는 1으로하고 마지막 원소까지 곱할 필요는 없다.
const leftArr = [
1,
1 * nums[0],
1 * nums[0] * nums[1],
1 * nums[0] * nums[1] * nums[2],
]; // [1, 1, 2, 6];
// @NOTE: 요소의 오른쪽까지의 곱을 기준으로 하기 때문에 직관적으로 역순으로 한다.
const rightArr = [
1 * nums[2] * nums[1] * nums[0],
1 * nums[2] * nums[1],
1 * nums[2],
1,
]; // [24, 12, 4, 1];Implementation(T=O(n), S=O(n))
위의 정리를 토대로 구현을 해보자.
- n 번째 원소의 왼쪽 곱의 값들을 저장한다.
- n 번째 원소의 오른쪽 곱의 값들을 저장한다.
- 전체 원소를 순회하며 n 번째 원소의 좌우 값의 곱을 저장한다.
- 리턴한다.
// Left Arr
const l = nums.reduce(
(acc, cur) => {
const last = acc[acc.length - 1]; // 누적값
acc.push(cur * last); // 이전의 누적값 * 현재 원소를 통해 누적값을 채운다.
return acc;
},
[1],
);
l.pop(); // 마지막 원소는 필요 없으므로 빼준다.
// Right Arr
const r = nums.reduce(
(acc, _, index) => {
const last = acc[0];
const cur = nums[nums.length - index - 1];
acc.unshift(cur * last);
return acc;
},
[1],
);
r.shift();
// Left * Right Arr
const answers = nums.map((_, index) => l[index] * r[index]);
return answers;위의 구현으로 문제를 해결할 수 있지만 공간 복잡도가 O(n)이기 때문에 더 최적화가 가능하다.
Implementation(T=O(n), S=O(1))
좌우 배열은 결국 마지막에 곱하기 위해서만 존재한다.
따라서 굳이 저장하지 않고 바로바로 곱해나가면 공간복잡도를 O(1)으로 줄일 수 있다.
const answers = [];
let last = 1;
// @NOTE: Step1. Answers 배열에 미리 왼쪽 곱 배열을 세팅
for (let i = 0; i < nums.length; i++) {
const cur = nums[i];
answers[i] = last;
last *= cur; // 누적값 갱신
}
last = 1;
// @NOTE: Step2. Answers가 이미 좌측 곱 배열이므로 우측 값을 그대로 곱해주면 정답이 된다.
for (let i = nums.length - 1; i >= 0; i--) {
const cur = nums[i];
answers[i] *= last;
last *= cur;
}
return answers;NOTE: 어쨌든 answers 배열을 사용하므로 정확히는 O(n)이지만
LeetCode에서 return 배열(answers)이 아닌 추가 배열을 사용하지 않는다는 것으로 O(1)으로 취급하고 있다.
연속되는 곱셈의 합을 이용한 재밌는 문제였다.
그럼 이만~