[Leetcode] 238. Product of Array Except Self - JS
1. 문제 분석
문제분석
--------------------
- 정수배열 nums
- answer 배열 반환
- answer[i]는 nums[i]를 제외한 모든 요소의 곱
- nums는 32bit 정수로 이루어져있다.
- 나누기 연산을 사용하지 않고 시간복잡도 O(n)이어야 한다.
제한조건
--------------------
- 2 <= nums.length <= 10^5
- -30 <= nums[i] <= 30
2. 접근 방법
접근방법
--------------------
nums 길이와 동일한 prefix, subfix 배열을 선언한다.
prefix 배열에는 현재 인덱스 이전의 요소들의 곱을 저장하고,
subfix 배열에는 현재 인데스 이후의 요소들의 곱을 저장한다.
마지막으로 answer 배열에 인덱스에 맞게 prefix와 subfix의 곱을 저장하여 반환한다.
3. 코드
var productExceptSelf = function(nums) {
const n = nums.length;
const prefix = Array.from({length: 1}, () => 1);
const subfix = Array.from({length: 1}, () => 1);
// 이후 요소들의 곱을 저장하니 0번째 다음부터 시작한다. 0번째 이전 값은 없으니...
for (let i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
};
// 이후 요소들의 곱을 저장하니 마지막 요소 전부터 역순으로 진행한다. 마지막 요소 다음 값은 없으니...
for (let i = n - 2; i >= 0; i--) {
subfix[i] = subfix[i + 1] * nums[i + 1];
};
const answer = [];
for (let i = 0; i < n; i++) {
answer[i] = prefix[i] * subfix[i];
};
return answer;
};단계별로 코드를 디버깅해보자.
========== 입력값 ==========
nums = [1,2,3,4]
========== 초기값 ==========
n = 4
prefix = [1,1,1,1]
subfix = [1,1,1,1]
========== prefix for 문 ==========
prefix[1] = prefix[0] * nums[0] = 1 * 1
prefix = [1,1,1,1]
prefix[2] = prefix[1] * nums[1] = 1 * 2 인데, prefix[1]은 prefix[0]을 포함하고 있다.
prefix = [1,1,2,1]
prefix[3] = prefix[2] * nums[2] = 2 * 3 인데, prefix[2]은 prefix[1]을 포함하고 있다.
prefix = [1,1,2,6]
위 반복문의 결과로 prefix의 각 요소는 0번째를 제외하고 이전 요소들의 곱을 저장하고 있다.
========== subfix for 문 ==========
subfix[2] = subfix[3] * nums[3] = 1 * 4
subfix = [1,1,4,1]
subfix[1] = subfix[2] * nums[2] = 4 * 3 인데, subfix[2]은 subfix[3]을 포함하고 있다.
subfix = [1,12,4,1]
subfix[0] = subfix[1] * nums[1] = 12 * 2 인데, subfix[1]은 subfix[2]을 포함하고 있다.
subfix = [24, 12, 4, 1]
위 반복문의 결과로 subfix의 각 요소는 마지막 요소를 제외하고 이후 요소들의 곱을 저장하고 있다.
마지막으로 answer에 인덱스에 맞게 prefix, subfix를 곱하면 해당 인덱스 요소를 제외한 나머지 요소들로만 구성된 곱을 구할 수 있다.
answer = [1 * 24, 1 * 12, 2 * 4, 6 * 1] = [24, 12, 8, 6]
4. 복잡도 분석
- 시간복잡도: O(n)
- 공간복잡도: O(n)
5. 공간 복잡도 개선 방법
앞선 풀이로는 prefix, subfix 배열을 선언하므로 공간 복잡도가 O(n)의 메모리를 소모한다.
이를 개선하여 answer만 선언하여 문제를 풀어보자.
접근 방법은 기존과 비슷하다.
접근방법
--------------------
answer 배열을 선언한다.
이전 또는 이후 요소들의 곱을 누적하는데 사용하는 product 변수를 선언한다.
인덱스 이전 요소들의 곱을 계산하여 answer에 추가한다.
product 변수를 초기화한 후
인덱스 이후 요소들의 곱을 계산하여 answer[i] 위치에 맞게 할당한다.
코드
--------------------
var productExceptSelf = function(nums) {
const n = nums.length;
const answer = [];
let product = 1;
// answer 배열에 이전 요소들의 곱을 추가한 뒤 현재 요소를 추가로 곱해준다.
// 그러면 다음 반복문 때 이전 요소들의 곱이 된다.
for (let i = 0; i < n; i++) {
answer.push(product);
product *= nums[i];
}
// 이후 요소들의 곱을 구하기 위해 초기화
product = 1;
// answer에는 이전 요소들의 곱이 할당된 상태
// 역순으로 순회하면서 이후 요소들 곱을 곱해준다.
// 이후 요소들의 곱을 얻기 위해선 answer에 할당한 후
// product에 현재 요소를 곱하여 다음 반복문 때 이후 요소들의 곱을 구할 수 있다.
for (let i = n - 1; i >= 0; i--) {
answer[i] *= product;
product *= nums[i];
}
return answer;
}단계별로 코드를 디버깅해보자.
========== 입력값 ==========
nums = [1,2,3,4]
========== 초기값 ==========
n = 4
answer = [ ]
product = 1
========== 첫번째 for 문 ==========
answer = [1], product = 1 * nums[0] = 1 * 1 = 1
answer = [1, 1], product = 1 * nums[1] = 1 * 2 = 2
answer = [1, 1, 2], product = 2 * nums[2] = 2 * 3 = 6
answer = [1, 1, 2, 6], product = 6 * nums[3] = 6 * 4 = 24
첫번째 for 문으로 answer에는 이전 요소들의 곱이 할당된 상태이다.
product를 1로 초기화하고 두번째 반복문을 수행한다.
========== 두번째 for 문 ==========
answer[3] = answer[3] * 1 = 6 * 1 = 6 , product = 1 * nums[3] = 1 * 4 = 4
answer[2] = answer[2] * 4 = 2 * 4 = 8 , product = 4 * nums[2] = 4 * 3 = 12
answer[1] = answer[1] * 12 = 1 * 12 = 12 , product = 12 * nums[1] = 12 * 2 = 24
answer[0] = answer[0] * 24 = 1 * 24 = 24 , product = 24 * nums[0] = 24 * 1 = 24
answer = [24, 12, 8, 6]
두번째 for 문을 통해 이전 요소들의 곱들에 이후 요소들의 곱을 곱해주어 결과값을 얻을 수 있게 되었다.
복잡도 분석
--------------------
시간복잡도: O(n)
공간복잡도: O(1) // answer를 제외하면