[LeetCode] Product of Array Except Self - Python

MinWoo Park·2021년 5월 11일

Algorithm

목록 보기

36/42

Algorithm Problem with Python — 36day

문제 설명 📖

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

정수 배열 번호가 주어지면 숫자[i]를 제외한 모든 숫자 요소의 곱과 같은 배열 응답을 반환합니다.

숫자의 접두사 또는 접미사의 곱은 32비트 정수에 적합하도록 보장된다.

제한사항

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up:

Could you solve it in O(n) time complexity and without using division?
Could you solve it with O(1) constant space complexity? (The output array does not count as extra space for space complexity analysis.)

입출력 예

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

문제 이해 🔑

리스틀를 입력받아 ouput[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하는 문제입니다.

Follow up을 보시면 나눗셈을 하지 않고 O(n)에 풀이하라고 나옵니다.

간단한 풀이로 떠오르는 모두 곱하여 자기 자신을 나누는 것은 안되니 자기 자신을 제외하고 왼쪽과 오른쪽의 곱셈 결과를 곱하는 풀이로 접근해야 합니다.

수도 코드 ✍️

자기 자신을 제외한 왼쪽의 곱셈 결과를 리스트로 만들어야 합니다.
미리 리스트를 만들어 둔 후 nums[i]를 제외한 왼쪽 편의 곱들을 리스트에 넣습니다.
1에서 구한 결과에 오른쪽 값을 차례대로 곱합니다.
오른쪽은 우에서 좌측으로 진행하니 range() 함수를 사용할 때 3번 째 인자로 -1을 줍니다.
오른쪽 값은 i가 감소하니 nums에 접근할 때 사용 가능합니다.
그래서 한 칸씩 좌측으로 이동할 때 마다 오른쪽 값에 nums[i]를 곱하면 됩니다.

코드 작성 ⌨️

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        # 왼쪽 곱셈
        for i in range(0, len(nums)):
            out.append(p)
            p = p * nums[i]
        print('out', out) # [1, 1, 2, 6]
        p = 1
        # 왼쪽 곱셈 결과(out)에 오른쪽 값(p)을 차례대로 곱셈
        for i in range(len(nums) - 1, 0 - 1, -1):
            out[i] = out[i] * p # p는 1, 4, 12, 24이 됨
            p = p * nums[i] 
        return out # [1, 1, 2, 6]과 [24, 12, 4, 1]이 만나 각 인덱스 별로 곱하여 [24, 12, 8, 6]이 답이 됨.