[알고리즘][Python] LeetCode 238 Product of Array Except Self 문제 풀이

문제 출처 : leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

---

문제 해석 : 배열에서 자기 자신을 제외한 모든 수들의 곱을 구하는 문제이다. 다만 나누기 연산을 활용하지 않아야 하면 시간 복잡도 O(n)에 풀 수 있도록 해야한다.

 

문제 풀이 : 배열 두개를 활용해서 앞에서부터의 곱 뒤에서 부터의 곱을 미리 계산해 놓은다음 자기 자신을 제외하고 양 쪽의 수를 곱하면 답을 구할 수 있다.

---

풀이 코드

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []

        front = [1]
        end = [1]

        for i in range(len(nums)-1):
            front.append(front[-1] * nums[i])
        for i in range(len(nums)-1, 0, -1):
            end.insert(0, end[0] * nums[i])

        for i in range(len(nums)):
            answer.append(front[i] * end[i])

        return answer

if __name__=="__main__":
    solution = Solution()
    nums = [1,2,3,4]
    print(solution.productExceptSelf(nums))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 LeetCode 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.