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.

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

Follow up: Can you solve the problem in $O(1)$ extra space complexity? (The output array does not count as extra space for space complexity analysis.)

예제 입출력

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

참고

문제 전문은 여기에서 읽으실 수 있습니다.

풀이 1

접근법

1. 정답을 $O(n)$ 안에 얻으려면, 각 원소에서 자기 자신을 제외한 배열의 곱 값을 $O(1)$ 안에 얻어야 합니다. 왜냐하면 배열의 각 원소를 순회하는 데 $O(n)$이 걸리기 때문입니다.
2. 그래서, 누적 곱의 값을 구하는 것이 필수적입니다(매 순회마다 새로 모든 원소의 곱을 계산하는 것이 아닌).
3. 그러나, 전체 곱을 구해놓고 매 순회 마다 자기자신으로 나누는 방식으로는 정답을 구할 수 없습니다. 0으로 나눌 수는 없기 때문입니다.
4. 누적 곱을 구하되, 왼쪽 누적 곱과 오른쪽 누적 곱을 따로 구해서 배열로 관리할 수 있습니다.
5. 예외 처리(양 끝 구간인 경우) 후 정답을 쉽게 구할 수 있습니다.
6. 예를 들어, nums = [1, 2, 3, 4] 일 때,

nums = [1, 2, 3, 4]
accum_left = [1, 2, 6, 24]
accum_right = [24, 24, 12, 4]
ans[i] = accum_left[i - 1] * accum_right[i + 1]
ans = [24, 1 * 12, 2 * 4, 6]
    = [24, 12, 8, 6]

구현 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        accum_left = nums[::]
        accum_right = nums[::]
        ans = []

        for i in range(n):
            if i != 0 :
                accum_left[i] *= accum_left[i - 1]
                accum_right[n - i - 1] *= accum_right[n - i]

        for i in range(n):
            if i == 0 :
                ans.append(accum_right[i + 1])
            elif i == n - 1 :
                ans.append(accum_left[i - 1])
            else:
                ans.append(accum_left[i - 1] * accum_right[i + 1])

        return ans

Complexity Analysis

• n: nums 의 길이
• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(n)$

풀이 1+

접근법

1. 추가 문제에 대한 답을 얻으려면, 배열을 리턴하는 배열 하나만 사용해야 합니다.
2. accum_left, accum_right로 좌우 배열곱을 관리하는 대신 accum이라는 변수 하나에 누적 곱 값을 담아 관리할 수 있습니다.

구현 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1 for _ in range(n)]
        accum = 1

        for i in range(n):
            ans[i] *= accum
            accum *= nums[i]

        accum = 1

        for i in range(n-1, -1, -1):
            ans[i] *= accum
            accum *= nums[i]

        return ans

복잡도 분석

• n: nums 의 길이
• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(1)$ 개선됨!

---

책에 있는 풀이

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2

접근법

1. 풀이 1+ 와 거의 유사합니다.

구현 코드

from typing import List

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, - 1, -1):
            out[i] = out[i] * p
            p = p * nums[i]
        return out