Product of Array Except Self

---

💬 문제

[문제 링크]

정수 배열 nums
각 인덱스를 제외한 나머지 인덱스 값의 곱을 담은 answer 반환
시간 복잡도는 O(n)이어야 하며 나누기를 사용 금지

✍️ 나의 풀이

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const len = nums.length;
    const prefix = new Array(len).fill(1);
    const suffix = new Array(len).fill(1);
    const answer = new Array(len);

    for (let i = 1; i < len; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }

    for (let i = len - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }

    for (let i = 0; i < len; i++) {
        answer[i] = prefix[i] * suffix[i];
    }
    
    return answer;
};

두 가지 배열을 만들어서 하나는 앞에서부터 시작, 하나는 뒤에서부터 시작한다.
각각 자신의 다음 혹은 이전 인덱스의 num 값과 현재 배열 값을 곱한다.
이후 두 배열의 값을 또 곱해서 answer에 담으면 완성

📌 결과

Accepted
Runtime 115ms (Beats 14.14%)
Memory 65.09MB (Beats 19.33%)

📚 러닝 포인트

처음에는 나누기 금지를 보지 못하고 전체 요소를 곱한 값으로 배열을 채워서 각 인덱스마다 자신의 값으로 나누는 방법을 썼었는데, 사실 0이 들어가는 순간 틀린 값을 가지기 때문에 실패했다. 근데 도저히 생각해도 중첩 for문을 안 쓰고 만들 수가 없길래 hint 칸을 열어봤다. 거기서 prefix, suffix product를 활용하라는 말을 보게 되어 바로 검색했더니 유레카!

https://www.geeksforgeeks.org/prefix-product-array/
https://www.geeksforgeeks.org/suffix-product-array/

우선 suffix는 오른쪽 인덱스의 값을 곱하는 순환을 한 다음에 본인의 값을 곱하는데, 이 단계만 삭제하면 될 것 같았고 반대로 prefix는 순환할 때부터 이전 값이랑 본인 값을 곱하길래 suffix처럼 이전 인덱스의 num 값이랑 prefix 값을 곱하면 되겠다 싶었고 실제로 예제 테케를 계산해보니 둘의 곱이 딱 정답이었다. 그러니까 결론적으로 prefix는 자신의 이전 값들을 곱하는 것이고, suffix는 자신의 다음 값들을 곱하는 것이었다. 여기서 본인의 값만 곱하지 않고 두 결과를 곱하면 정답!

물론 힌트를 사용했기 때문에 이번에도 온전히 나의 알고리즘은 아니지만 그래도 눈치채고 만들었다는게 좀 뿌듯하다.