[LeetCode] 238. 자신을 제외한 배열의 곱(Product of Array Except Self)

배열을 입력받아 Output [i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.

 

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

 

*단, 나눗셈을 하지 않고 O(n)에 풀이하라.

 

 

 

 

사실 좀 어려워서 고민하다가 풀이 제목을 봤다.

보통 저 문제를 풀면 바로 떠오르는 것은

for문을 중복하여 곱해 나간다던지

전체를 곱하고 요소에서 나눠준 값을 넣는다던지가 있는데

전자는 시간 복잡도가 O(n^2)이 돼버리기에 안되고

후자는 문제 주인장이 그렇게 쉽게 풀지 말래서 안된다. ㅋ~

 

 

 

 

1. 내가 직접 푼 코드

 

left = []
    right = []
    result = []
    p = 1
    if len(nums) == 2:
        return [1 * nums[1], 1 * nums[0]]
    for i in range(len(nums)):
        if i == 0 and nums[i] != 0:
            left.append(1)
        elif i == 0 and nums[i] == 0:
            left.append(0)
        else:
            p *= nums[i - 1]
            left.append(p)
 
    p = 1
    for i in range(len(nums)):
        if i == 0:
            right.append(1)
        else:
            p *= nums[-i]
            right.append(p)
    right.reverse()
    print(right)
 
    for i in range(len(nums)):
        result.append(left[i] * right[i])
    return result

 

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]
        p = 1
        # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
        for i in range(len(nums) - 1, 0 - 1, -1):
            out[i] = out[i] * p
            p = p * nums[i]
        return out

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]