개요

LeetCode #238, Product of Array Except Self 문제를 풀어봅니다.

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up:

• Could you solve it in O(n) time complexity and without using division?
• Could you solve it with O(1) constant space complexity? (The output array does not count as extra space for space complexity analysis.)

나눗셈을 쓰지 마라고 합니다. 다 곱해놓고 나눠야 간단한데 막아버렸습니다. 왼쪽에서부터 곱해서 가장 뒤 원소를 빼고 차례로 곱해서 리스트 하나를 만듭니다. 그 결과물에 오른쪽에서부터 곱해서 가장 앞 원소를 빼고 차례로 곱합니다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # do not use division
        # nums = [1,2,3,4]
        # p1 = [1, 1, 2, 6] : product from left end. 1*1, 1*2, 1*2*3
        # p2 = [24, 12, 4, 1] : product from right end. 1*4, 1*4*3, 1*4*3*2
        # p = [24, 12, 8, 6] : p1 * p2 elementwise
        
        out = []
        p = 1
        # left product
        for i in range(0, len(nums)):
            out.append(p)
            p = p * nums[i]
        
        p = 1
        
        # right product
        # nums = [1,2,3,4] then p: 1 4 12 24
        for i in range(len(nums)-1, -1, -1):
            out[i] = out[i] * p
            p = p * nums[i]
        
        return out