Array : Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

prefix : 왼쪽으로부터의 누적곱

suffix : 오른쪽으로부터의 누적곱

이걸 이용해서 i에서의 answer은 i -1 까지의 prefix와 i + 1까지의 suffix의 곱으로 구하면 된다.

 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = [1] * len(nums)

        prefix = suffix = 1

        for i in range(1, len(nums)):
            prefix *= nums[i - 1]
            suffix *= nums[-i]

            result[i] *= prefix
            result[-i - 1] *= suffix

        return result

 

사실상 O(N)