[Leetcode] 238. Product of Array Except Self_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '238. Product of Array Except Self'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Product of Array Except Self' 알고리즘 문제

 

STEP 2. 'Product of Array Except Self' 코드(code)

 

STEP 3. 'Product of Array Except Self' 해설

 

STEP 4. 'Product of Array Except Self' solution

 

반응형

 

STEP 1. 'Product of Array Except Self' 알고리즘 문제

 

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.

 

정수 배열 nums가 주어지면, 답변[i]가 nums[i]를 제외한 nums의 모든 요소의 곱과 동일하도록 배열 답변을 반환합니다. nums의 접두어나 접미어의 곱은 32비트 정수에 맞도록 보장됩니다.
나누기 연산을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

 

Constraints:

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

 

---

STEP 2. 'Product of Array Except Self' 코드(code)

 

■ Runtime: 273ms Beats 45.28%
■ Memory: 25.68MB Beats 87.31%

 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
    
    	# Answer List to store the result
        answer_lst = [1] * len(nums)
        
        # Store the product of elements until the previous one
        temp_p, temp_s = 1, 1
        
        # Store forward product
        for idx, num in enumerate(nums[:-1]):
            temp_p *= num
            answer_lst[idx+1] = temp_p 

        # Store backword product, multiplying each not calculated from the forward pass
        for idx, num in enumerate(nums[::-1][:-1]):
            temp_s *= num
            answer_lst[-idx-2] *= temp_s 

        return answer_lst

---

STEP 3. 'Product of Array Except Self' 해설

 

문제의 제약 조건은 나누기 연산을 사용하지 않고, time complexity가 O(n) 알고리즘을 만드는 것입니다. nums array에 자기 자신 index를 제외한 모든 값을 곱해서 계산해야 되기에, array를 한 번에 이동하면서 계산하는 것은 어렵습니다.

 

array를 두 번 통과하여, 최초에는 index를 기준으로 낮은 index 값을 곱하고 (store forward product),

그리고 index를 기준으로 높은 index 값을 곱하는 (store backward prdocut) O(2n) 알고리즘을 적용했습니다.

 

 

STEP 4. 'Product of Array Except Self' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

list의 이전 index 값을 불러와서 계산하지 않고, 변수를 활용하여 list 호출하는 횟수를 줄임으로써 runtime 속도가 개선된 것을 확인할 수 있습니다.

 

■ Runtime: 267ms Beats 64.67%
■ Memory: 25.77MB Beats 52.02%

 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix_product = 1
        postfix_product = 1
        result = [0]*n
        for i in range(n):
            result[i] = prefix_product
            prefix_product *= nums[i]
        for i in range(n-1,-1,-1):
            result[i] *= postfix_product
            postfix_product *= nums[i]
        return result

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '238. Product of Array Except Self'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)