.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Plain Text
복사
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Plain Text
복사
Constraints:
•
2 <= nums.length <= 10^5
•
30 <= nums[i] <= 30
•
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
My solution
정수 배열 nums가 주어지면 answer 배열이 반환된다. 이 때 answer[i]는 nums[i]를 제외한 nums의 모든 요소의 곱과 같다.
nums의 prefix나 suffix의 곱은 32비트 정수에 맞게 보장됩니다.
division 연산을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
JavaScript
복사
nums가 주어지고,
0번 인덱스는 그 인덱스의 요소를 제외한 모든 요소의 곱이 들어간다. 즉, 2 * 3 * 4 = 24
1번 인덱스는 1 * 3 * 4 = 12
2번 인덱스는 1 * 2 * 4 = 8
3번 인덱스는 1 * 2 * 3 = 6
수학적인 공식을 찾아내야 하는 문제다. 한번 떠올리지 못하면 풀지 못하는 문제일 수 있다.
for문을 2번 돈다.
첫 for문에서는 answer 배열에 이전 숫자들을 가지고 곱해서 재할당한다.
const LEN = nums.length;
const answer = [...Array(LEN)].fill(1);
// store prefix product
for (let i = 1; i < LEN; i++) {
answer[i] = answer[i - 1] * nums[i - 1];
}
console.log(answer);
JavaScript
복사
왼쪽에서 오른쪽으로 한번 채워넣는 과정이다.
이후 오른쪽(마지막 요소)에서 왼쪽(첫 요소)까지 곱하면서 값을 완성한다.
이 때 suffixProduct가 필요하다. 이 값은 nums[i]를 곱한 값으로 매번 루프마다 업데이트된다.
하지만 두번째 케이스에 답이 -0 때문에 틀리게 된다.
하지만 걱정을 하지말자.
Jest에서는 틀리다지만 콘솔에서 찍어보면 0이나 +0이나 -0이나 다 똑같다고 해준다!
Code
/**
* @param {number[]} nums
* @return {number[]}
*/
const productExceptSelf = function (nums) {
const LEN = nums.length;
const answer = [...Array(LEN)].fill(1);
// store prefix product
for (let i = 1; i < LEN; i++) {
answer[i] = answer[i - 1] * nums[i - 1];
}
for (let i = LEN - 1, suffixProduct = 1; i >= 0; i--) {
answer[i] *= suffixProduct; // multiply stored prefix product with suffix product
suffixProduct *= nums[i]; // update suffix product
}
return answer;
};
describe('productExceptSelf', () => {
it('TC1', () => {
expect(productExceptSelf([1, 2, 3, 4])).toStrictEqual([24, 12, 8, 6]);
});
it('TC2', () => {
expect(productExceptSelf([-1, 1, 0, -3, 3])).toStrictEqual([0, 0, 9, 0, 0]);
});
});
JavaScript
복사
