[코테] 리트코드 배열 238. Product of Array Except Self

238. Product of Array Except Self

문제 링크

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

문제 설명

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.

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

제한 사항

• 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.

입출력 예 #1

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

입출력 예 #2

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

문제 풀이

자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱하면 된다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        # 왼쪽 곱셈
        for i in range(0, len(nums)):
            out.append(p)
            p = p * nums[i]
        p = 1
        # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
        for i in range(len(nums) - 1, 0 - 1, -1):
            out[i] = out[i] * p
            p = p * nums[i]
        return out