[LeetCode][Python] 238. Product of Array Except Self

- 문제 링크: https://leetcode.com/problems/product-of-array-except-self/

- 난이도: Medium

 

배열에서 각 원소마다 그 원소를 제외한 다른 원소를 전부 곱한 값을 반환하는 문제다

You must write an algorithm that runs in O(n) time and without using the division operation.

이런 단서조항이 써있어서, 다른 방식으로 풀어야 한다

 

누적합 방식과 비슷하게 누적곱으로 만들면 되는데, 본인을 제외한 곱셈값이 필요하니 왼쪽, 오른쪽이 필요하다

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ret = []

        product = 1
        for i in range(len(nums)):
            ret.append(product)
            product *= nums[i]

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

        return ret