[파이썬 알고리즘 인터뷰] - 7장 p.193 (Leet Code 238번)

 

 

 

 

 

 

 

 문제

 

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

 

 

 

 

 

 

 문제 상황

 

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

 

- 나눗셈을 하지 않고 O(N)에 해결한다.

 

 

 

 

 

 

 해결 전략

 

- 두가지 방향으로 곱을 쌓아 나가 연산한다.

 

 

 

 

 

 

 코드

 

from typing import List
 
 
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        temp = 1
        for i in range(len(nums)):
            result.append(temp)
            temp *= nums[i]
        temp = 1
        for i in range(len(nums)-1, -1, -1):
            result[i] *= temp
            temp *= nums[i]
        return result

 

 

 

 

 

 

 

 

 해설

 

- 예시 [1, 2, 3, 4]를 양방향을 기준으로 곱한 결과물을 곱한 결과물이 구하고자 하는 결과값이 된다.

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 양 방향에서 마지막 값은 어차피 곱해지지 않으니 끝까지 곱할 필요가 없다.