[LeetCode] 238. Product of Array Except Self 해설 및 풀이 (Python)

LeetCode 238. Product of Array Except Self

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

 

---

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.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

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]

 

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

한글 번역)

238. 자신을 제외한 배열의 곱

정수 배열 nums가 주어졌을 때, answer[i]가 nums[i]를 제외한 나머지 모든 요소의 곱이 되도록 배열 answer를 반환하세요.

어떤 prefix(앞부분)나 suffix(뒷부분)의 곱도 32비트 정수에 저장할 수 있음이 보장됩니다.

단, 나눗셈 연산은 사용하지 않고, 시간 복잡도는 O(n)으로 작성해야 합니다.

 

예시 1:

• 입력: nums = [1,2,3,4]
• 출력: [24,12,8,6]

예시 2:

• 입력: nums = [-1,1,0,-3,3]
• 출력: [0,0,9,0,0]

 

제약 조건:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• answer[i]는 32비트 정수로 표현할 수 있음이 보장됩니다.

 

추가 질문:

이 문제를 공간 복잡도 O(1)로도 해결할 수 있나요? (출력 배열은 공간 복잡도 계산에서 제외됨)

 

---

 

문제 유형

배열

구간 합

 

풀이 방법 도출

 

정수 배열 nums가 주어졌을 때 answer[i]는 nums[i]를 제외한 모든 원소들의 곱이 되도록 배열 answer를 만들어야 합니다.

단, 나눗셈을 사용하지 않아야 하며 시간 복잡도는 O(n)이어야 합니다.

 

처음엔 전체 곱을 구해서 answer[i] = total_product / nums[i] 방식도 있지만

이 문제에서는 나눗셈 사용 금지 조건 때문에 사용 불가능합니다.

 

따라서 왼쪽 곱과 오른쪽 곱을 따로 계산하는 방식을 통해서 문제를 해결하려고 합니다.

 

1. answer[i]는 nums[i]를 제외한 왼쪽의 곱 × 오른쪽의 곱으로 구성됩니다. (예: nums = [1, 2, 3, 4], answer[2] = (1 * 2) * (4) = 2 * 4 = 8)
2. left_product를 1로 시작해서 왼쪽부터 차례대로 곱을 누적하면서 answer[i]에 저장하여 왼쪽 곱을 계산합니다.
3. right_product를 1로 시작해서 오른쪽부터 누적하면서 기존 answer[i]에 곱해주어 오른쪽 곱을 계산합니다.

 

 

시간 복잡도

• 왼쪽 곱 계산 : O(N)
• 오른쪽 곱 계산 : O(N)
• 총 시간 복잡도 : O(N)

---

핵심 코드 삽입 및 설명

from typing import List

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

        # 왼쪽 곱 계산
        left_product = 1
        for i in range(n):
            answer[i] = left_product
            left_product *= nums[i]

        # 오른쪽 곱 계산
        right_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right_product
            right_product *= nums[i]

        return answer