.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
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 <=
•
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
product of all the elements of nums except nums[i].
nums[i]를 제외한 nums의 모든 요소들의 곱이 i번째 요소가 된다.
모든 접두사 또는 접미사의 숫자는 32비트 정수에 맞도록 보장됩니다.
분할 연산? 나눗셈 연산 없이
Input:
1563847412
Output:
2147483651
Expected: 0
Plain Text
복사
내가 믿는 최대 32비트 정수 (2^31)는 2,147,483,647입니다. 이것은 음수 값 (-2^31)이 32비트 제한 으로 저장될 수 있도록 하기 위한 것입니다 (이것이 "서명된"의 의미임).
나눗셈 연산 없이 구하라는 것은 모든 요소를 미리 다 곱해놓고 해당 nums로 나눈 값을 다시 배열에 집어 넣는 것을 말하는 것 같다.
이렇게 되면 모든 배열을 전부 순회하면서 모든 요소의 곱을 구하는 것이 O(n)만큼 들 것이고,
그다음 배열의 각 원소를 하나씩 방문하면서 구해두었던 모든 요소의 곱을 각 원소로 한번씩 나누면서 배열에 집어 넣어야 되서 O(n)만큼 더 써야 한다.
TC1 :
[1,2,3,4]
Output: [24,12,8,6]
이 경우를 보면 1,2,3,4를 전부 곱해서 24를 만들어놓고 [24/1, 24/2, 24/3, 24/4]가 가능하다.
TC2:
[-1,1,0,-3,3]
Output: [0,0,9,0,0]
이 경우에 division operation을 쓰는 게 안 통한다.
[ 9/-1, 9/1, 9/0, 9/-3, 9/3 ] = [-9, 9, NaN, -3, 3]이 된다.
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.)
이건 뭘까? 공간복잡도 0(1) 내에서 해결하라고 한다.
0이 포함된 경우) 0을 만날 때 모든 요소의 곱을 넣는다. + 0을 안 만나면 전부 0일 수 밖에 없다.
0이 없는 경우) 모든 요소의 곱과 나눈 값을 넣기.
⇒ [0, 0] ⇒ [1, 1]이 나옴 fail
pre[i] contains product of all nums[j] such that j <= i, and suf[i] contains product of all nums[j] such that j >= i.
ans는 ans[i] = pre[i-1] * suf[i+1]로 계산할 수 있으며, 이는 지수가 i보다 작은 모든 요소의 곱에 지수가 i보다 큰 모든 요소의 곱을 곱한 값입니다. 이는 각 인덱스에서 자신을 제외하고 어레이의 곱과 기본적으로 동일합니다.
ans에 prefix products를 모은다.
const productExceptSelf = function (nums) {
const n = nums.length;
const ans = [...Array(n)].fill(1);
// store prefix product
for (let i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
JavaScript
복사
ans[i-1]은 전부 1이 들어있는데 ans에 담을 때는 이전 값들을 가지고 만들어낸다.
[-1, 1, 0, -3, 3] → [1, -1,,,,,] // ans는 그냥 1이고 nums[i-1]은 -1이니까 ans[1]에 ans[0](=1) * -1부터 들어간다.
[-1, 1, 0, -3, 3] → [1, -1, -1, ,,,] // ans[i] = ans[i-1](= -1) * nums[i-1](= 1) = -1
,,,
for (let i = n - 1, suffixProd = 1; i >= 0; i--) {
ans[i] *= suffixProd; // multiply stored prefix product with suffix product
suffixProd *= nums[i]; // update suffix product
}
JavaScript
복사
suffixProd는 1부터 시작한다. 뒤에서부터 계산한다.
ans[i] = ans[n-1] (맨 뒤)에서부터 ans에 곱해서 ans를 바꾼다.)
suffixProd *= nums[i];를 통해서 suffixProd가 늘어난다. 기존 nums는 변한 게 없다. 이게 계속 곱이 누적된다. 처음에는 1이지만 한칸만 이동해도 3이 된다.
뒤에서 두번쨰까지는 원래가 0이라서 0으로 그대로 남는다.
세번쨰부터는 -9가 된 상태라서 ans에다가 곱해서 넣으면 9가 된다. , suffix는 nums[2]를 곱해서 업데이트되는데 이값이 0이라서 suffix는 0이 되버린다.
네번쨰는 방금 0이 된 suffix에다가 ans를 곱해서 넣으면 0이 된다. suffix는 nums[1]를 곱해서 업데이트되는데 기존에 0이었고 nums[1]가 1이므로 둘을 곱하면 0이 된다.
마지막으로 방금 0이 된 suffix에다가 ans[0]( = -1)을 곱한다. 그럼 -0이 된다.
결과적으로 [-0, 0, 9, -0, 0]이 된다.
[0, 0]
ans를 1로 채운 배열로 만든다.
ans[i] = ans[i - 1] * nums[i - 1];를 for문으로 순회한다.
1) ans[1] = ans[0] * nums[0] = 1 * 0 = 0
ans = [1, 0]이 된다.
(let i = n - 1, suffixProd = 1; i >= 0; i--)로 for문 순회
ans[i] *= suffixProd하면 ans[n-1] = ans[1] = 0인데 suffixProd가 1이지만 결국 ans[n-1] = 0이 된다.
suffix *= nums[i] 는 기존 1에다가 nums[i](원본배열)nums[1](= 0)이 곱해져서 들어간다. suffixProd = 0;
ans[0] *= suffixProd하면 ans[0]은 1이고 suffixProd는 0인 상태니까 ans[0]이 0이 되버린다.
suffixProd *= nums[i]를 계산해야된다. 지금의 suffixProd는 0인 상태고 nums[0]은 0이다. 둘을 곱하면 0이 된다.
결과적으로 [0,0]이다.
위의 로직은 굉장히 빠르다. 하지만 수학적으로 고민을 많이 해야됐다. 어떻게 풀었는지 신기하다.
ans라는 새로운 배열이 하나 필요하고 기본값이 1로 초기화되어 있어야 한다.
이건 이전인덱스의 nums의 요소의 영향을 받는다. ans의 영향도 받게 되는데 이 ans는 ans[1](0번인덱스는 제외)부터 채우기 시작한다. 이렇게 이전 인덱스의 값들을 영향 받게 되면 prefix product를 구할 수 있음을 쉽게 알 수 있다.
두번째로 suffix product를 구하는 로직이다. suffixProd라는 변수가 필요하다는 점이 중요하다. 처음에는 1이다. 구해뒀던 ans를 맨 뒤에서부터 업데이트한다. 처음에는 1에다 곱해주겠지만 그다음부터 suffixProd로 suffix product를 누적시켜 만들어주기 위해서 nums[i](=nums[n-1])를 갖다쓴다.
이렇게 좌측에서 쭉 놀리고, 우측에서 좌측으로 한번 쭉 놀리면 구해뒀던 ans 배열의 prefix product를 활용해서 suffix product를(1부터,, 요소가 1개라면 1이 맞음) 곱해서 누적시킬 수 있다.
답은 아래와 같이 나오는데 -0이여도 0으로 취급해줘서 leetCode에서는 pass해준다. jest에서는 안된다.
소스코드
/**
* @param {number[]} nums
* @return {number[]}
*/
const productExceptSelf = function (nums) {
const n = nums.length;
const ans = [...Array(n)].fill(1);
// store prefix product
for (let i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
for (let i = n - 1, suffixProd = 1; i >= 0; i--) {
ans[i] *= suffixProd; // multiply stored prefix product with suffix product
suffixProd *= nums[i]; // update suffix product
}
return ans;
};
// test('TC1', () => {
// expect(productExceptSelf([1, 2, 3, 4])).toStrictEqual([24, 12, 8, 6]);
// });
test('TC2', () => {
expect(productExceptSelf([-1, 1, 0, -3, 3])).toStrictEqual([0, 0, 9, 0, 0]);
});
// test('TC3', () => {
// expect(productExceptSelf([0, 0])).toStrictEqual([0, 0]);
// });
JavaScript
복사
