[파이썬 알고리즘 인터뷰] 자기 자신을 제외한 배열의 곱 | 리스트, 선형 자료구조

박상길, 『파이썬 알고리즘 인터뷰』를 정리한 내용입니다.

 

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

Product of Array Except Self - LeetCode

---

문제 요약

• 자기 자신을 제외한 나머지 모든 요소의 곱셈결과가 담신 배열을 구하라
• 단, 나눗셈을 하지 않고 O(n)에 풀이하라

---

풀이 전략

❗️나눗셈을 사용할 수 없기 때문에 모든 요소의 곱에서 자기 자신을 나눠서 답을 구하는 전략은 사용할 수 없다...!!😟

 

0 ~ i-1번째까지의 곱셈결과와 i+1 ~ n-1까지의 곱셈결과를 곱하는 전략을 사용한다

• for i in range(1, N)인 동안 answer[i]에는 인덱스가 i보다 작은 요소들의 곱셈 결과를 저장한다
• for i in range(N-1, -1, -1)인동안 p에는 인덱스가 i보다 큰 요소들의 곱셈 결과를 저장하고 answer[i]에 p를 곱한다.

---

소스코드

교재의 코드에서 내가 이해하기 쉽게 코드를 아주 조금 수정했다

class Solution:
    def productExceptSelf(self, nums: [int]):
        N = len(nums)
        answer = [1]
        for i in range(1, N):
            answer.append(answer[i-1]*nums[i-1])

        p = 1
        for i in range(N-1, 0, -1):
            answer[i] *= p
            p *= nums[i]

        return answer