[리트코드/leetcode/python] 238. Product of Array Except Self

이미지를 누르면 문제 링크를 보실 수 있습니다

이 문제를 푸는 것에 있어서 O(n^2)으로는 바로 풀 수 있겠지만, 결과적으로 시간초과가 나고, follow up을 보면, 공간복잡도를 O(1)로 풀기를 제안하고 있습니다.

 

처음에 제가 접근한 방식은 배열의 길이를 2배로 늘려서 [1,2,3,4] 가 인풋 배열이라면, [1,2,3,4,1,2,3,4] 로 만든 후, 1을 바라볼 때는, [2,3,4] 의 곱을 2를 바라볼 때는 [3,4,1], 3을 바라볼 때는 [4,1,2], 4를 바라볼 때는 [1,2,3] 을 곱해서 결과 배열을 만드려고 했습니다.

위와 같은 방식으로 문제를 풀 때, 많은 변수들이 필요했고, 파이썬의 for문을 돌면서, index를 다시 뒤로가도록 하는 것에 있어서 어려움을 겪었습니다.

 

결국, 저는 문제를 O(n)의 방식으로 30분만에 풀지 못하였는데, 최대한 코드를 이해해보려고 Discussion을 통해 문제풀이힌트를 살펴봤습니다. O(n)의 시간복잡도를 가진 풀이는 크게

1) 0이 몇개 포함되어 있는지에 따라 if문으로 분기를 만드는 방법과

2) 순회 원소 기준으로 왼쪽과 오른쪽 원소를 모두 곱한 값을 결과배열에 입히는 방법이 있었습니다.

 

저는 전자보다 후자의 풀이해석에 집중했습니다.

이 때도, 메모리를 덜 사용하기 위해, left와 right에 해당하는 배열을 두 개 만들지 않고, 하나의 배열에 한 번에 값을 입히도록 설정했는데요, 풀이코드는 아래와 같습니다.

 

class Solution(object):

    def productExceptSelf(self, nums):

	# example input_array => [1,2,3,4]
        
	answer = [] 

        # left    
        p = 1		# initial p
        
        for idx in range(len(nums)):
            answer.append(p)
            p *= nums[idx]

        # current answer = [1,1,2,6]
    

        # right

        p = 1		# initial p
        
        for idx in range(len(nums)-1,-1,-1):
            answer[idx] = p * answer[idx]
            p *= nums[idx]
            
        # right = [24,12,4,1]    
        # final answer = [24,12,8,6]
     
        return answer

주석을 통해, 이해하기 쉽도록 구간을 나눠봤습니다.

 

# left

먼저 순회하는 원소 기준으로 left에 있는 원소들의 누적곱을 answer 배열에 더합니다.

 

0번째 인덱스는 시작 인덱스므로 처음에는 1이 들어갈 수 밖에 없습니다. 

(위의 예시 [1,2,3,4] 중에 1을 바라볼 때는 왼쪽에 아무것도 없으니, 1을 append하게 됩니다.)

 

그 다음부터 p*= num[index] 와 같이 각 배열의 원소를 누적해서 곱하면서 p를 갱신함과 동시에 answer배열에 append합니다.

[1,2,3,4]에 대하여 left에 대한 계산을 했을 때, 배열은 [1,1,2,6] 이 됩니다.

 

 

# right

다음은 바라보는 원소 기준으로 오른쪽 배열을 살펴봅시다.

 

이 때는 오른쪽을 계산해야하므로, 끝 원소부터 처음원소까지 거꾸로 돌면서 누적곱을 해결해야 합니다.

이 때, left = [] 배열과 right= [] 배열처럼 다 하고, 나중에 서로 원소끼리 곱하는 시도도 해봤지만, 이 또한 시간초과가 나서, 기존 left 계산을 하고 갱신이 된 배열에 그대로 right 누적곱을 입혔습니다.

 

left를 보면 마지막 왼쪽 끝원소에 대한 값은 기존 끝원소를 제외한 왼쪽의 모든 누적값이 값으로 할당되어 있습니다.

right를 바라볼 때, 마지막 원소의 값에 1을 곱한 값을 가장 먼저 할당하고 시작하는데요, 

맨 끝 원소 기준으로 오른쪽에는 아무것도 없으니, 끝원소와 1을 곱한 값이 들어가는게 적절합니다.

 

그 다음은 left를 바라볼 때 처럼, 바라보는 원소 기준 오른쪽의 누적값을 할당하면서 0번째 인덱스까지 순회합니다.

 

이렇게 모든 Left, Right 순회가 끝나면, 결과 배열은 answer에 담기게 되고, 그대로 반환을 해주면 됩니다!

시간복잡도를 줄이는 코드를 고민하면서 어떻게 하면 복잡도를 줄이는 알고리즘을 짤 수 있을지 배울 수 있는 시간이었던 것 같습니다.

 

이상으로, 누적곱과 관련한 Product of Array Except Self 문제를 정리해봤습니다.