[배열] 자신을 제외한 배열의 곱

* leetcode 238. Product of Array Except Self

 

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

# 입력
[1, 2, 3, 4]

# 출력
[24, 12, 8, 6]

# 나눗셈을 하지 않고 O(n)으로 풀이하라.

---

풀이 1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

# 자신을 제외한 왼쪽 곱셈 결과
# [1, 1, 2, 6]

# 자신을 제외한 오른쪽 곱셈 결과
# [24, 12, 4, 1]

# 이 둘을 곱하면
# [ 1,  1, 2, 6]
# [24, 12, 4, 1]

# [24, 12, 8, 6] -> 답

def productExceptSelf(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