[DSA][Array & Hashing] 06. Product of Array Except Self

LeetCode 238

 

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

 

 

[질문하기]

- 배열에 0이 하나 이상 포함될 수 있나요?

 

 

[아이디어]

- 0의 개수가 중요하다!

- 각 원소를 기준으로 왼쪽과 오른쪽 곱을 구하자

 

 

[풀이 1] Division

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        productAll = productExceptZero = 1
        zeroCnt = 0
        for i in nums:
            productAll *= i
            if i == 0:
                zeroCnt += 1
            else:
                productExceptZero *= i
        if zeroCnt <= 1:
            return [productExceptZero if i == 0 else int(productAll / i) for i in nums]
        else:
            return [0] * len(nums)

처음 문제를 보면 "원소 다 곱한 다음에 각 원소로 나누면 되는 거 아니야?"라는 아이디어가 생각날 수 있다.

하지만 이 방식은 nums에 0이 포함되면 전체 곱이 0으로 되어버리고, 곱을 0으로 나눌 수도 없기 때문에 동작하지 않는다.

 

따라서 위의 방식은 세 가지 CASE에 따라 처리 방식이 달라진다.

1) 0이 하나도 없을 때

원소 전체의 곱을 구한 뒤에 각 원소의 값으로 나눈다.

 

2) 0이 1개 일 때

0인 원소만 나머지 원소의 곱이고, 나머지 원소들은 전부 0을 반환한다.

 

3) 0이 2개 이상일 때

자기 자신을 제외한 나머지 원소들의 곱은 항상 0이다.

 

⏱️ 시간복잡도

원소를 한번 순회하기 때문에 O(n)

🧠 공간복잡도

nums의 원소 개수만큼의 공간이 필요하므로 O(n)

 

 

[풀이 2] Prefix, Suffix

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [1] * n
        right = [1] * n

        for i in range(1, n):
            left[i] = left[i - 1] * nums[i - 1]
            right[n - i - 1] = right[n - i] * nums[n - i]
        
        output = [1] * n
        for i in range(n):
            output[i] = left[i] * right[i]

        return output

except nums[i]라는 것은 결국 nums[i]를 기준으로 왼쪽 원소들의 곱과, 오른쪽 원소들의 곱을 곱하는 것이다.

따라서 왼쪽의 누적곱과 오른쪽의 누적곱을 배열에 저장한 뒤에, 두 배열에서 같은 인덱스의 원소의 곱을 구하면 된다.

 

ex) [1, 2, 3, 4]

left = [1, 1, 2, 6]

right = [24, 12, 4, 1]

output = [1 * 24, 1 * 12, 2 * 4, 6 * 1] = [24, 12, 8, 6]

 

⏱️ 시간복잡도

원소를 한번 순회하기 때문에 O(n)

🧠 공간복잡도

nums의 원소 개수만큼의 공간이 필요하므로 O(n)