[파이썬 알고리즘] 7장 배열 - 자신을 제외한 배열의 곱 (product of array except self)

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

Product of Array Except Self - LeetCode

 

<문제>

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

 

<예시>

Input: [1,2,3,4]

Output: [24,12,8,6]

 

---

이것도 아쉬움이 많았던 문제 ...

왜 생각하지 못 했을까 ...

 

• 각 index 기준 오른쪽에 위치한 값의 누적 곱 - O(n)
  • 가장 끝에서부터 누적해서 곱해가면 된다
• 각 index 기준 왼쪽에 위치한 값의 누적 곱 - O(n)
  • 가장 앞에서부터 누적해서 곱해가면 된다
• 각 index 기준 오른쪽에 위치한 값의 누적 곱 * 왼쪽에 위치한 값의 누적 곱 구하면 끝 - O(n)

 

def solution_1(nums: List[int])->List[int]:
    # i index의 왼쪽에 위치한 모든 값의 곱
    left_product = []
    product = 1
    for value in nums:
        left_product.append(product)
        product *= value

    # i index의 오른쪽에 위치한 모든 값의 곱
    right_product = []
    product = 1
    for value in nums[::-1]:
        right_product.insert(0, product)
        product *= value

    result = []
    for i in range(len(nums)):
        # i index의 왼쪽에 위치한 모든 값의 곱 * 오른쪽에 위치한 모든 값의 곱
        result.append(left_product[i]*right_product[i])
    return result