Leetcode 238: 자신을 제외한 배열의 곱

배열을 입력받아 output[i]가 자신을 제외한
나머지 모든 요소의 곱셈 결과가 되도록 출력하라.

*주의
나눗셈을 하지 않고 O(n)에 풀이하라

Product of Array Except Self - LeetCode

// 입력 예제
[1,2,3,4]

// 출력 예제
[24,12,8,6]

 

 

 

 

오답

Time limit exceeded

 

import math
    
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        arr = []
        result = []
        
        for i in range(len(nums)):
            arr = nums.copy()
            arr.remove(nums[i])
            result.append(math.prod(arr))
        return result

 

자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과라는 solution 힌트를 보고 풀어봤는데 

또 다시 시간초과가 나왔다.

 

import math
    
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        result = []
        
        # 자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈결과
        for i in range(len(nums)):
            print(i)
            arr = []
            arr.append(math.prod(nums[:i]))
            arr.append(math.prod(nums[(i+1):]))

            result.append(math.prod(arr))
        return result

 

 

 

풀이

 

1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

 

변수 i 가 오른쪽으로 이동하면서 해당 인덱스의 값을 곱해 나간 다음, 오른쪽에서 
곱해서 넣는다. 여기서 만약 별도의 리스트 변수를 만들고 그 변수에 우측 곱셈 결과를 넣으면,
공간 복잡도는 O(n)이 된다. 그러나 기존 out 변수를 재활용한다면 공간 복잡도 O(1)에 풀이가 가능하다.
  

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