[Leetcode] 238. Product of Array Except Self

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

Product of Array Except Self - LeetCode

풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
		
        # 왼쪽 인덱스부터 차례대로 곱을 계산
        left_product = [1] * n
        for i in range(1, n):
            left_product[i] = left_product[i-1] * nums[i-1]

        # 오른쪽 인덱스부터 차례대로 곱을 계산
        right_product = [1] * n
        for i in range(n-2, -1, -1):
            right_product[i] = right_product[i+1] * nums[i+1]

	# 각 인덱스에서 자신을 제외한 왼쪽, 오른쪽 곱을 곱셈
        for i in range(n):
            result[i] = left_product[i] * right_product[i]

        return result

이번 문제는 prefix sum 알고리즘을 활용한 문제였다. 정확히는 prefix multiply(?)이다.

 

먼저 왼쪽, 오른쪽 인덱스를 기준으로 차례대로 곱하기를 한 두 배열을 만들어준다. 만약 [1, 2, 3, 4]라는 배열이 주어졌다고 가정하면, left_product는 [1, 1, 2, 6]이 되고, right_product는 [24, 12, 4, 1]이 된다.

 

그런 다음 각 인덱스에서 left_product, right_product의 값을 가져와 곱해주면 해당 인덱스를 제외한 모든 인덱스의 곱을 가진 배열이 완성된다.