문제
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4] Output: [24,12,8,6] Note: Please solve it without division and in O(n).
Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
풀이
배열에서 본인을 제외한 나머지 원소들의 곱을 구해야 하는 문제이다.
생각의 흐름
처음에는 배열의 모든 원소를 곱한다음에 각 원소를 나눠주면 본인을 제외 할 수 있다고 생각했지만 문제에서 나눗셈으로 풀지 말라고 명시해두었다.
그래서 다른 방법을 생각해봤는데, 어쨌든 각 원소들의 곱셈을 구해야 하는건 무조건 해야하는일인데 가장 무식하게 생각했을때,
output[0]값을 구하기 위해서 input[1] ~ input[3] 까지 곱하고
output[1]값을 구하기 위해서 input[0], input[2], input[3] 을 곱하고
그때그떄 곱하는 방법이 가장 먼저 생각났다. 근데 이렇게 알고리즘을 짜면 중복되는 계산을 너무 많이 하게 된다.
output[0]을 구하기 위해서 계산했었던 input[2] * input[3]값을
output[1]값을 구할때 활용하지 못하고 쓸데없이 한번더 계산해버리게 된다.
그래서 곱셈의 결과를 메모이제이션 하면 최적화 할 수 있을거라 생각했다.
어떤식으로 메모이제이션할지 고민해본 결과 배열 두개를 준비해서
mult1에는 왼쪽부터 오른쪽으로
mult2는 오른쪽에서 왼쪽으로 곱셈값을 채워나간다.
그리고 나서 output[i]를 구하기 위해서 mult1[i-1]과 mult2[i+1]을 곱하면 나름 효율적인 솔루션이 될것이라고 생각했다.
var productExceptSelf = function(nums) {
const mult1 = [],
mult2 = [],
output = [];
const len = nums.length;
for (let i = 0; i < len; i++) {
mult1[i] = i == 0 ? nums[i] : mult1[i - 1] * nums[i];
mult2[len - 1 - i] = i == 0 ? nums[len - 1] : nums[len - i - 1] * mult2[len - i];
}
for (let i = 0; i < len; i++) {
output[i] = i != 0 && i != len - 1 && mult1[i - 1] * mult2[i + 1];
}
output[0] = mult2[1];
output[len - 1] = mult1[len - 2];
return output;
};예외처리
배열의 길이는 2이상이므로 아무 숫자나 길이 2로 넣어서 테스트해본 결과 예외가 발생하지 않을것이라고 예상했다.
결과
