https://leetcode.com/problems/product-of-array-except-self/
Product of Array Except Self - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
핵심 아이디어
- result[i]의 값은 왼쪽 부분(prefix)의 곱과 오른쪽 부분(postfix)의 곱을 곱한 것이다
- prefix[i]와 postfix[i] 는 각자 이전 값에다 nums[i]를 곱하면 되기 때문에 O(1) 시간에 구할 수 있다
- result array에 prefix 값을 쓰고, 다시 반대로 읽으면서 postfix 값을 쓰면서 공간 복잡도를 O(1)으로 줄일 수 있다
- result array는 어차피 답 출력할 때 써야 하는 array이므로 공간 복잡도 계산에 포함되지 않는다
복잡도
- 시간 복잡도: O(n)
- 배열을 순방향, 역방향으로 2회 순회
- 이전 값에 누적하며 곱하는 방식으로 prefix 구하기 O(n) + 반대 방향으로 postfix 곱하면서 채우기 O(n)
- 공간 복잡도: O(1)
- 출력할 때 쓰는 result array를 활용 (공간 복잡도 계산 x)
- prefix 변수 O(1), postfix 변수 O(1)
설명
코드 (Javascript)
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
let result = Array(nums.length);
let prefixProduct = 1;
for (let i = 0; i < nums.length; i++) {
result[i] = prefixProduct;
prefixProduct *= nums[i];
}
let postfixProduct = 1;
for (let i = nums.length - 1; i >= 0; i--) {
result[i] *= postfixProduct;
postfixProduct *= nums[i];
}
return result;
};
유튜브 NeetCode 해설 영상
'Problem Solving' 카테고리의 다른 글
[LeetCode] 152. Maximum Product Subarray (JS) (0) | 2022.08.21 |
---|---|
[LeetCode] 53. Maximum Subarray (JS) (0) | 2022.08.07 |
[LeetCode] 217. Contains Duplicate (JS) (0) | 2022.07.31 |
[LeetCode] 121. Best Time to Buy and Sell Stock (JS) (0) | 2022.07.02 |
[LeetCode] 1. Two Sum (JS) (0) | 2022.07.02 |