[Leetcode]_238. Product of Array Except Self

문제

https://leetcode.com/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150 

LeetCode - The World's Leading Online Programming Learning Platform

풀이

접근 방법은 다음과 같다.

// 오답코드!
def productExceptSelf(nums):
    answer = [0 for i in range(len(nums))]
    multiplyOfElem = 1
    for i in range(len(nums)):
        multiplyOfElem *= nums[i]
    
    for i in range(len(nums)):
        answer[i] = multiplyOfElem // nums[i]

    return answer

• 첫번째 for 문에서 요소들의 곱을 구한다.
• 두번째 for 문에서 answer 배열의 요소를 현재 요소로 나눈 몫으로 할당해주었다.

하지만 위 경우 [-1,1,0,-3,3] 에서 처럼 요소가 0인 경우 모든 요소의 곱이 항상 0이기 때문에 모든 경우의 수를 만족할 수 없다.

 

고민끝에 다른 사람의 풀이를 참고했다.

• 위 사진에서 자기 자신을 기준으로 이전 요소들의 곱이 prefix 요소로 들어가게된다.
  • prefix[0]은 prefix[-1]이 1로 가정하고 nums[1]과의 곱이 할당된다.
  • prefix[1]은 prefix[0] * nums[1]이 할당된다.
  • prefix[2]은 prefix[1] * nums[2]이 할당된다.
  • prefix[3]은 prefix[2] * nums[3]이 할당된다.
• 마찬가지로 postfix는 뒤에서 부터 순회하여 할당된다.
  • postfix[3]은 postfix[4]를 1로 가정하고 nums[3]과의 곱이 할당된다.
  • postfix[2]은 postfix[3] * nums[2]이 할당된다.
  • postfix[1]은 postfix[2] * nums[1]이 할당된다.
  • postfix[0]은 postifx[1] * nums[0]이 할당된다.
• 결과배열의 요소는 현재 요소 이전 인덱스의 prefix와 현재 요소 다음 인덱스의 postfix의 곱으로 나타낼 수 있다.
  • output[0] = prefix[-1] * postfix[1]
  • output[1] = prefix[0] * postfix[2] ...

• 그런데 굳이 prefix, postfix를 생성하지 않고 처음 순회하면서 prefix 값을 output 배열에 할당한다.
• 두번째는 뒤에서부터 순회하면서 output 결과값에 postfix 값을 곱해주면 된다.

 

정답코드

def productExceptSelf(nums):
    res = [1] * (len(nums))
    
    prefix = 1
    for i in range(len(nums)):
        res[i] = prefix
        prefix *= nums[i]
    
    postfix = 1
    for i in range(len(nums)-1,-1,-1):
        res[i] *= postfix
        postfix *= nums[i]
    return res

 

참고자료

 

https://youtu.be/bNvIQI2wAjk?si=eKPmSjfEPzzd2Qer