leetcode 238 - Product of Array Except Self

 

배열을 순회하면서 각 idx에 있는 수를 제외한 나머지들을 모두 곱한 값을 출력하는 문제

게다가 문제에서도 O(n)의 시간복잡도로 풀이를 하라고 되어있다.

 

[1,2,3,4]의 경우는 [ 2*3*4 , 1*3*4, 1*2*4, 1*2*3] 인 [24, 12, 8, 6] 이 답인 것이다.

이는 뒤집에서 생각해보면, [1*2*3*4 / 1 , 1*2*3*4 / 2 , 1*2*3*4 / 3 , 1*2*3*4 / 4] 의 계산으로도 가능하기 때문에, 전체 의 곱인 24를 구하고 각 1,2,3,4로 나누면 되는 것이다.

 

이때 주의해야 하는 점이 리스트에 0이 포함되는 경우이다. [-1, 1, 0, -3, 3]인 경우, 모든 곱을 하게 되면 0이 나오니 위의 로직을 그대로 따른 다면 [0, 0, 0, 0, 0]이 나오게 되기 때문에 예외처리가 필요하다.

 

또 한가지 더 예외처리가 필요한 부분은 주어진 리스트에 0이 2개 포함된 경우이다.

예를 들어 [0, 1, 0, 3, 4] 로 주어진다면 어떤 index에서든 자기 자신의 index를 제외한 다른 수에도 적어도 1개의 0은 존재하기 때문에 이때는 계산할 필요도 없이 [0, 0, 0, 0, 0]를 반환하면 된다.

 

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = []
        product = 1
        
        if 0 not in nums:
            for num in nums:
                product = product * num

            for num in nums:
                result.append(product / num)
            return result
        elif nums.count(0) >= 2:
            return [0]* len(nums)
        else:
            idx = nums.index(0)
            rr = nums[:]
            del rr[idx]
            
            for n in rr:
                product = product * n
            
            result = [0] * len(nums)
            result[idx] = product
            return result