[leetcode] 238. Product of Array Except Self 파이썬 코드

자신의 인덱스를 제외한 나머지 숫자들의 곱을 계산하는 문제이다.

O(n)으로 작성해야 하며 나눗셈은 쓸 수 없다.

 

첫 번째 방법, prefix와 postfix 배열 사용하기

 

 

prefix = [0] * len(nums)
postfix = [0] * len(nums)
output = [0] * len(nums)

for i in range(len(nums)):
    if i > 0:
        prefix[i] = prefix[i-1] * nums[i]
    else:
        prefix[i] = nums[i]

for i in range(len(nums)-1, -1, -1): # i = 3, 2, 1, 0
    if i < len(nums) - 1:
        postfix[i] = postfix[i+1] * nums[i]
    else:
        postfix[i] = nums[i]

for i in range(len(nums)):
    # check i
    if i-1 < 0:
        output[i] = postfix[i+1]
    elif i+1 > len(nums)-1:
        output[i] = prefix[i-1]
    else:
        output[i] = prefix[i-1] * postfix[i+1]

 

 

조금 더 효율적으로 짤 수는 없을까?

 

prefix, postfix 리스트를 사용하지 않고, output 배열 하나에만 담을 수도 있다.

 

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

        prefix_val = 1
        for i in range(len(nums)-1): # i = 0, 1, 2, 3
            prefix_val *= nums[i]
            output[i+1] = prefix_val

        postfix_val = 1
        for i in range(len(nums)-1, 0, -1): # i = 3, 2, 1
            postfix_val *= nums[i]
            output[i-1] *= postfix_val

        return output