Leetcode 238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

 

---

 

처음 접근)

import math
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []
        total = math.prod(nums)
        if 0 not in nums:
            return [int(total/i) for i in nums]
        else:
            for i in range(len(nums)):
                if nums[i] == 0:
                    answer.append(math.prod(nums[:i])*math.prod(nums[i+1:]))
                else:
                    answer.append(0)
            return answer
            
        #return [math.prod(nums[:i])*math.prod(nums[i+1:]) for i in range(len(nums))]
        --> 단순 prod 를 이용한 계산으로 TLE 발생

이 문제는 비교적 단순한 array 문제였는데요, 처음에는 단순 연산으로 한줄 구현했다가 

이후에 time complexity를 줄이기 위해 0이 아닐 때는 먼저 계산한 (전체 요소들의 곱)/각 원소의 값으로 연산을 줄이고

0이 있는 경우에는 계산 없이 0을 넣도록 해서 계산을 단순화했습니다.

 

---

 

다른 분들은 어떻게 Time complexity를 줄였는지 볼까요?

 

def productExceptSelf(self,nums):
	prod, zero_cnt = reduce(lambda a,b: a*(b if b else 1), nums,1), nums.count(0)
    
    if zero_cnt > 1: return [0]*len(nums)
    
    for i, c in enumerate(nums):
    	if zero_cnt: nums[i] = 0 if c else prod
        else: nums[i] = prod // c
    return nums

reduce 함수로 연산을 prod 변수에 담아주고

0d이 1개 이상 있으면 전체를 0으로 깔아주고  그 다음에 for문을 이용해서 나머지 값을 채워주는 형식을 사용했습니다

 

  def productExceptSelf(self, nums):
        ans, suf, pre = [1]*len(nums), 1, 1
        for i in range(len(nums)):
            ans[i] *= pre               # prefix product from one end
            pre *= nums[i]
            ans[-1-i] *= suf            # suffix product from other end
            suf *= nums[-1-i]
        return ans

두 번째 코드는 ans와 pre를 따로 업데이트 하고 곱해서 해당 원소를 제외한 곱이 계산되도록 했습니다

 

흠,, 표현의 차이일 뿐 접근 방식은 크게 다르지 않은 것 같네요!