Leetcode Product of Array Except Self 문제 풀이 with python

List 문제

위 문제의 핵심은 O(n) 시간 복잡도로 자신의 위치를 제외한 모든 항목의 값을 곱한 값을 구해야 한다.

• 2중 반복문 사용 X

처음에는 모든 값을 곱한 값을 구하고, 이를 각 위치의 원소로 나누어서 계산하려고 했다. 하지만 원소의 범위가 음수, 0, 양수 모든 값을 포함하고 있어서 해당 방식으로 처리할 수 없었다. (정수를 0으로 나눌 수 없기 때문이다.)

 

그래서 해당 문제를 각 항목의 위치를 기준으로 왼쪽의 있는 값을 모든 곱한 값과 오른쪽의 있는 값을 모든 곱합 값을 곱하여 (본인 위치에 있는 값을 제외한 값) 원하는 값을 O(n) 시간 복잡도로 해결할 수 있었다.

output = [1 for _ in range(len(nums))]
left, right = 1, 1

• output 리스트는 모든 값을 1로 초기화하여 곱셈의 영향을 가지지 않도록 합니다.
• left는 왼쪽부터 곱하기 시작하는 값 / right는 오른쪽부터 곱하기 시작하는 값

for i in range(len(nums)):
    output[i] *= left  # 현재 위치의 왼쪽에 있는 모든 값 곱하기
    left *= nums[i]    # left update

먼저, 현재 위치의 왼쪽에 있는 값을 곱합니다.

 

ex) [1, 2, 3, 4] 인 경우에

초기값	1	2	3	4
ouput	1	1	2	6

 

맨 왼쪽에 있는 값에는 left한 값이 없으므로 1을 그대로 곱합니다. 2번째에 위치한 값에는 왼쪽에 있는 값 left를 곱합니다.

… N번째까지 같은 방법을 반복합니다.

 

해당 방법을 통해 현재 위치의 값을 기준으로 왼쪽에 있는 모든 값을 구할 수 있습니다.

이제 오른쪽에 있는 값만 모두 곱한 값을 알면 자신을 제외한 모든 값을 구할 수 있습니다.

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

초기값 1 2 3 4

초기값	1	2	3	4
(left) ouput	1	1	2	6
right	24	12	4	1
(right) ouput	24	12	8	6

 

right도 left와 동일하게 오른쪽에 있는 값을 모두 곱한 값을 구합니다.

 

문제 핵심

0을 나눌 수 없는 것을 확인하고, 리스트의 값을 한 번만 순회해서 문제를 풀어야 한다.

특정 값을 기준으로 삼아 원하는 값을 만들 수 있는지 생각할 수 있어야 한다.

 

정답

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        output = [1 for _ in range(len(nums))]
        left, right = 1, 1

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