알고리듬 : LeetCode 238. Product of Array Except Self

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

input
[1,2,3,4]
output
[24,12,8,6]

조건
나눗셈을 하지 않고 O(n)에 풀이하라.

풀이:
이중 반복문을 사용하면 효율성에서 실패한다.
배열에서 index i에 대해
i의 왼쪽 원소의 모든 곱 A
i의 오른쪽 원소의 모든 곱 B로 나누어 구한다음
A*B로 답을 구해야한다.

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

list 'out'에 왼쪽 곱을 append 후, 오른쪽 곱을 곱해준다다.

코드에서 주의하여 파악할 부분은 p를 후위연산을 한다는 점이다.

이전까지 원소들의 곱 결과를 현재 원소에 먼저 append하거나 곱해주고 나서 p값을 연산해준다.

Thought:

나눗셈과 시간복잡도의 제약조건이 있어서 까다롭다.
접근법을 떠올리는 것 자체가 어려웠던 문제인듯 했다.