https://leetcode.com/problems/product-of-array-except-self/description/
기본 목표는 나눗셈을 하지 않고 O(n)을 달성하는 것이다.
당연히 2중 for문은 불가하다.
나눗셈을 쓰지 말라는 것은 왜일까?
nums의 총합을 곱해 total을 찾아놓고, 해당 인덱스 값을 나누면 너무 쉽기 때문인 듯.
1이라는 값을 사용해서 self 인덱스를 계산하면 되겠다고 떠올렸으나
구현에서 어려움이 있어서 바로 solution 참고
아이디어는 맞은 듯, prefix/suffix로 1값을 패딩넣고 본인 빼서 계산하는 아이디어다.
그 경우 추가 배열을 만들고 i-1 또는 i+1을 통해 밀어 쓰는 방식인데,
솔루션중에 공간복잡도를 더 적게 쓰는 방법이 있어서 참고했다.
ans 배열을 1로 모두 초기화해두고 누계를 곱한다.
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int ans[] = new int[n];
Arrays.fill(ans, 1);
int curr = 1;
// left 계산
for (int i=0; i<n; i++) {
ans[i] *= curr;
curr *= nums[i];
}
// right 계산
curr = 1;
for (int i=n-1; i>=0; i--) {
ans[i] *= curr;
curr *= nums[i];
}
return ans;
}
}나눗셈 없이 해야하는게 목표기 때문에 prefix 혹은 suffix를 넣고 한칸씩 밀어 계산해야 하기 때문에 left한 번, right 한 번이 필요하다.
left -> self 기준으로 왼쪽을 모두 곱한 누계를 self index에 누적
right -> self의 오른쪽을 모두 곱한 누계를 다시 곱함
알기쉽게 nums = [1,2,3,4]일 때 ans 배열에 대해 Sysout을 찍어보면 아래와 같다.
(left 1)
[1, 1, 1, 1]
(left 2)
[1, 1, 1, 1]
(left 3)
[1, 1, 2, 1]
(left 4)
[1, 1, 2, 6]
(right 1)
[1, 1, 2, 6]
(right 2)
[1, 1, 8, 6]
(right 3)
[1, 12, 8, 6]
(right 4)
[24, 12, 8, 6]
