자기 자신을 제외한 모든 원소들의 곱들을 산출하시오.
https://leetcode.com/problems/product-of-array-except-self/

• 단, 나눗셈을 하지 않고 O(n)에 풀이하시오.

22-05-30

import numpy as np

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        answer = np.array([1]*len(nums))
        for i,n in enumerate(nums):
            multiplication = answer*n - answer
            multiplication[i] = 0
            answer += multiplication
        
        return answer
        

array로 각 원소의 곱만큼 더하기 방식으로 진행했다.
단, 해당 원소는 0을 더함으로 조건을 만족하였다.
하지만, Time Out. ㅎㅎ
array 자체로 계산하는 것이 O(n)...

Next to do.
1. 왼쪽 곱셈에 결과에 오른쪽 값을 차례대로 곱셈하는 방식으로 풀자

24-09-11

import numpy as np 
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        n = len(nums)
        
        answer = np.array([1]*n)

        for i, num in enumerate(nums):

            backup = answer[i]
            answer *= num
            answer[i] = backup

        return answer

자기 자신에 해당하는 인덱스만 backup으로 남겨둔 후, 어레이의 모든 값에 숫자를 곱함.
그 이후 해당 인덱스에 backup 값으로 다시 대체함.

Next What to Do
1. 2*O(n) 으로 푼다고 생각
2. 정방향 O(n) + 역방향 O(n)