[오답노트] LeetCode #238 Product of Array Except Self

교훈

• LeetCode 문제 링크
• 출처 : 박상길 저, 파이썬 알고리즘 인터뷰, p.193

문제

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

answer[i]에는 nums[i]를 제외한 다른 모든 요소의 곱이 들어간다.

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

nums의 요소들은 모두 32비트 정수다.

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

O(n)에 풀어야 하며, 나눗셈을 사용해서는 안된다.

Example 1:

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

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

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

발상

Solution #1. O(n^2)에 풀기

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ret = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                ret[i] *= nums[j]
        return ret

Solution #2. 나눗셈 사용하기

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        p = 1
        for i in range(len(nums)):
            p *= nums[i]
        ret = [p] * len(nums)
        for i in range(len(ret)):
            ret[i] //= nums[i]
        return ret

일단 나눗셈을 사용했으므로 틀린 답안이지만, 알고리즘 자체에도 오류가 있다.

nums의 요소 중에 0이 하나라도 있으면 틀린다.
1. p = 0을 가지게 되므로 ret 배열은 0으로 채워지고, 아무리 다른 값으로 나눠봤자 값을 되찾을 수 없다.
2. nums[i]가 0이라면 ZeroDivisionError에 빠진다.

따라서, 처음부터 p를 계산할 때 0이 들어있는 경우는 빼고 계산하여야 한다.
굳이 만들어보자면 다음과 같은 코드가 나온다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        p = 1
        zero_appeared = False
        zero_idx = -1
        for i in range(len(nums)):
            if nums[i] == 0:
                if zero_appeared: # 0이 두개
                    return [0] * len(nums)
                zero_appeared = True
                zero_idx = i
                continue
            p *= nums[i]

        if zero_appeared: # 0이 1개
            ret = [0] * len(nums)
            ret[zero_idx] = p
            return ret
            
        ret = [p] * len(nums)
        for i in range(len(ret)):
            ret[i] //= nums[i]
        return ret

Success
Runtime: 224 ms, faster than 97.56% of Python3 online submissions for Product of Array Except Self.
Memory Usage: 21.2 MB, less than 58.64% of Python3 online submissions for Product of Array Except Self.

통과는 했다...
아쉽게도 LeetCode 채점 서버에는 나눗셈 연산자를 사용했는지 판별하는 기능은 없었다.

Solution #3

[a, b, c, d, e]가 있다고 해보자.

한번 순회를 하면서
[1, a, a*b, a*b*c, a*b*c*d]을 가지는 새로운 배열을 만들어보자.

이번에는 역으로 순회를 하면서
[e*d*c*b, e*d*c, e*d, e, 1]을 가지는 새로운 배열을 만들어보자.

이 새로운 배열 2개를 스칼라곱(내적)하면,
[(e*d*c*b), (e*d*c)*(a), (e*d)*(a*b),(e)*(a*b*c), (a*b*c*d)]
를 얻을 수 있다. 이거 생각한 사람은 진짜 천재다.

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

에 대해 생각해보자면,
두번째 새로운 배열은 굳이 만들 필요 없이 첫번째 새로운 배열에 덮어씌우는 식으로 만들고, 곱해지고 있는 값은 p라는 변수 하나에 계속 갱신하면 된다.

풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ret = []
        p = 1
        for i in range(len(nums)):
            ret.append(p)
            p *= nums[i]
        
        p = 1
        for i in range(len(nums) - 1, - 1, -1):
            ret[i] *= p
            p *= nums[i]
        return ret