[LeetCode] 238. product_of_array_except_self (Medium) 2023/5/2

 

문제 제목	정답률	난이도
238. product-of-array-except-self	65.1%	Medium

Product of Array Except Self - LeetCode

 

문제요약

배열의 요소 중 자신을 제외한 나머지의 곱셈 결과를 가지는 새로운 배열을 출력하라

조건 1) 32비트 정수형 숫자 배열이 주어진다

조건 2) 나눗셈을 사용하지 않도록 한다

조건 3) 시간 복잡도가 $ O(n) $ 이내여야 한다

 

 

생각했던 풀이 1(시간초과) : 왼쪽 배열, 오른쪽 배열 나눠서 곱한다 -> 새로운 함수 정의

 

생각했던 풀이 2 : 왼쪽 배열, 오른쪽 배열 나눠서 곱한다 -> for 구문

 

 

풀이 1(시간초과)

Step1. 배열이 주어지면 곱 출력 -> lambda

 

Step2. 해당 원소를 제외하여 왼쪽 오른쪽으로 나누어 배열 전달 -> 슬라이싱 이용

 

 

구현

from functools import reduce
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        def multiply(arr):
            return reduce(lambda x, y: x * y, arr)

        result=[]
        if len(nums)<=1:
            return []
        if len(nums)==2:
            return nums[::-1]
        for idx in range(0, len(nums)):
            if idx==0:
                result.append(multiply(nums[1:]))
            elif idx==len(nums)-1:
                result.append(multiply(nums[:len(nums)-1]))
            else:
                result.append(multiply(nums[:idx])*multiply(nums[idx+1:]))
        return result

 

 

풀이 2  (232ms)

반복문을 이용해서 왼쪽, 오른쪽 곱을 나누어 곱하기

 

Step1. 왼쪽 배열의 곱을 결과에 저장

 

Step2. 저장된 결괏값에 오른쪽 배열의 값의 곱의 결과를 기존 배열에 곱한다

 

 

구현 (232ms)

class Solution:     
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result=[]
        next_left=1
        #왼쪽 원소의 곱을 결과에 추가
        for value in nums:
            result.append(next_left)
            next_left*=value
        #오른쪽값 곱을 결과에 곱함    
        next_right=1
        for idx in range(len(nums)-1, -1, -1):
            result[idx]*=next_right
            next_right*=nums[idx]

        return result

 

예외처리 1(+15ms)

배열의 크기가 매우 작을 경우 따로 예외처리를 해 보니 오히려 처리 속도가 증가하였다.

        if len(nums)<=1:
            return []
        if len(nums)==2:
            return nums[::-1]