238. Product of Array Except Self

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

Product of Array Except Self - LeetCode

Solution

class Solution:
    def productExceptSelf(self, nums):
        if nums.count(0) > 1:
            return [0]*len(nums)

        idx = -1
        total = 1
        for i, n in enumerate(nums):
            if n==0:
                idx = i
            else:
                total *= n

        if idx != -1:
            ans = [0 for _ in range(len(nums))]
            ans[idx] = total
            return ans

        ans = []
        for n in nums:
            ans.append(int(total/n))
        return ans

• nums에 0이 2개 이상 있으면 리스트에 0만 채워서 반환한다.
• 처음부터 끝까지 0을 제외하고 곱해서 total에 저장한다. 0이 나오면 해당 인덱스를 idx에 저장한다.
• idx에 값이 들어있다면 0이 있으므로 0이 있는 곳만 total을 넣고 반환한다.
• idx에 값이 없다면 0이 없으므로 처음부터 끝까지 자신을 나눈 값을 넣는다.

Another

class Solution:
    def productExceptSelf(self, nums):
        output = [1] * len(nums)
        L = len(output)

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

        r = 1
        for i in range(L-1, -1, -1):
            output[i] = output[i] * r
            r = r * nums[i]
        return output

• 아래의 예시를 통해 이해할 수 있다.
  • nums : [1 2 3 4 5]
  • Pass 1: [  -      1      12     123  1234]
  • Pass 2: [2345  345    45      5      -   ]
  • Pass 3: [2345, 1345, 1245, 1235, 1234]
  • 첫 for문에서 Pass 1을 계산하고, 두 번째 for문에서 Pass 3를 계산하여 답을 구한다.