[leet_code] 238. Product of Array Except Self

오현우·2022년 4월 5일
0
post-thumbnail

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.

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 product of any prefix or suffix of nums 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.)

항상 문제를 잘봐야한다.

You must write an algorithm that runs in O(n) time and without using the division operation.
라는 조건이 주어졌는데 본인은 아래와 같은 코드를 작성했다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        num_product = 1
        cnt = 0
        answer = []
        for i in nums:
            if i != 0:
                num_product *= i
            if i == 0:
                cnt += 1
        
        if cnt >= 2:
            answer = [0] * len(nums)
            return answer
        
        for i in nums:
            if cnt == 1:
                if i == 0:
                    answer.append(num_product)
                else:
                    answer.append(0)
                
            else:
                answer.append(num_product // i)
                
        return answer

위의 코드는 시간복잡도는 지켰지만, 문제의 조건인 나누기를 쓰지 말라는 조건을 어겼다.

해결 방법

num = [a, b, c, d, e] 라고 가정해보자. (모두 정수임.)

그렇다면 우리는 resolution = [bcde, acde, abde, abce, abcd] 로 나오는 알고리즘을 구성해야 한다.

잘보면 어느 분기점으로 해당 문자를 분할할 수 있을 것 같아 보인다.

[|bcde, a|cde, ab|de, abc|e, abcd|] 이제야 규칙이 조금 보인다.

그렇다면 [1, a, ab, abc, abcd] , [bcde, cde, de, e, 1] 이 두 리스트를 element wise하게 곱해주면 해결이 완료 된다고 볼 수 있다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []
        left_list = [1]
        right_list = [1]
        
        ### left part
        temp = 1
        for left in nums:
            temp = temp * left
            left_list.append(temp)
        
        else:
            left_list.pop()
        
        ### right part 
        temp = 1
        for right in nums[::-1]:
            temp = temp * right
            right_list.append(temp)
            
        else:
            right_list.pop()
            right_list = right_list[::-1]
            
        
        for left, right in zip(left_list, right_list):
            res.append(left * right)
        
        return res
    

공간 복잡도를 더 줄일 수 있다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []
        
        p = 1
        for i in range(len(nums)):
            res.append(p)
            p = p * nums[i]
        
        p = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] = res[i] * p #1
            p = p*nums[i]
        
        return res

해당 알고리즘의 순서

[1, a, ab, abc, abcd] 로 리스트 생성

[1, a, ab, abc, abcd] > [1, a, ab, abce, abcd] > [1, a, abde, abce, abcd] >
[1, acde, abde, abce, abcd] > [bcde, acde, abde, abce, abcd]

res 라는 하나의 리스트만을 사용해 사용공간을 최소화 하였다.

profile
핵심은 같게, 생각은 다르게

0개의 댓글