[LeetCode] 238. Product of Array Except Self

🔗 Problem Link

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

---

❔Thinking

• 배열이 주어지면, 자신의 원소를 제외한 모든 원소의 곱을 배열에 담아 반환한다.
• 나누기 연산 없이, O(n)의 시간복잡도를 가지는 알고리즘을 작성해야 한다.

---

💻Solution

def productExceptSelf(self, nums: List[int]) -> List[int]:
    left, right = 1, 1
    n = len(nums)
    answer = [1] * n
    for i in range(n):
        answer[i] *= left
        left *= nums[i]
    for i in range(n-1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

---

🗝️keypoint

1. 자신을 제외한 원소의 곱은, 자신을 기준으로 왼쪽과 오른쪽의 값을 모두 곱하는것이다.
2. 나누기 연산을 사용할 수 있는 경우에도, 0으로 나누는 경우가 발생하기 때문에 유의해야 한다.