1. 문제

문제링크 : https://leetcode.com/problems/product-of-array-except-self

2. 풀이

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

        for i in range(len(nums)):
            output.append(product)
            product *= nums[i]
        
        product = 1

        for i in range(len(nums)-1, -1, -1):
            output[i] *= product
            product *= nums[i]
        
        return output

나누기 연산을 사용하지 않고 자신을 제외한 원소의 곱을 구하기 위해선 nums의 i번째 원소 왼쪽 부분의 곱과 오른쪽 부분의 곱을 구할 수 있어야 한다. 이를 위해서 반복문 두 개를 사용하는데, 첫 번째 반복문에선 output의 i번째 원소의 값이 nums의 i번째 원소 기준으로 왼쪽의 모든 원소를 곱한 값이 되도록 output에 곱을 저장한다. 오른쪽 부분은 두 번째 반복문에서 product에 nums의 원소를 곱하면서 구한다. product 값을 output 리스트의 오른쪽 원소부터 반복하며 곱하다 보면 결국 문제가 원하는 output이 완성된다. nums 크기만큼 반복하는 반복문 두 개가 중첩되지 않고 존재한다. 따라서 이 풀이의 시간 복잡도는 $O(n)$이 되므로 문제에서 요구하는 시간 복잡도를 충족시킨다.