productExceptSelf

# output 의 요소는 nums 에서 자기자신을 제외한 나머지 요소의 곱
# output[0] = nums[1]*nums[2]*nums[3]
# output[1] = nums[0]*nums[2]*nums[3]
# output[2] = nums[0]*nums[1]*nums[3]
# output[3] = nums[0]*nums[1]*nums[2]

# nums = [1, 2, 3, 4]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        output = []

        for index in range(0, len(nums)):
            left = 0
            right = len(nums)-1
            product = 1

            while left < index:
                product = product*nums[left]
                left += 1

            while right > index:
                product = product*nums[right]
                right -= 1
            output.append(product)

        return output

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        output = []

        value = 1
        for index in range(0, len(nums)):
            output.append(value)
            value = value * nums[index]

        value = 1
        for reverse_index in range(len(nums)-1, 0, -1):

            output[reverse_index] = output[reverse_index]*value
            value = value * nums[reverse_index]

        return output

# 시간복잡도를 줄이려면 ?

# 반복문 안에서 왼쪽 곱하고, 오른쪽 곱하면 시간복잡도가 n^2 이 되므로

# 미리 왼쪽 곱한 배열을 준비하고

# 오른쪽 곱한 값을 곱한 후 리턴 하면 2n 에 가능

# nums = [1,2,3,4]

# cf> 왼쪽 0 번째는 무조건 1 오른쪽 마지막 번째는 무조건 1
# left = [1,1,1*2,1*2*3]
# right = [2*3*4,3*4,4,1]
# output = [24,12,8,6]

# range(start,end,step)
# end 는 포함되지 않음

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        output = []

        value = 1
        for index in range(0, len(nums)):
            output.append(value)
            value = value * nums[index]

        value = 1
        for reverse_index in range(len(nums)-1, -1, -1):

            output[reverse_index] = output[reverse_index]*value
            value = value * nums[reverse_index]

        return output