[LeetCode] 238. Product of Array Except Self (C++)

문제

 

https://leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

 

풀이

 

난이도: Medium 

 

주어지는 배열에서 자신(nums[i])의 값을 제외한 나머지 값을 곱한 값을 answer[i]로 구하는 문제이다.

단, 제한사항으로 풀이의 알고리즘은 O(n)의 시간 복잡도를 가지고 나눗셈 연산을 사용해서는 안된다.

 

You must write an algorithm that runs in O(n) time and without using the division operation.

 

나눗셈 연산을 사용하면 굉장히 쉽지만 제한사항을 따라서 다음과 같이  O(n)의 시간 복잡도에 풀 수 있다.

 

배열의 i번째의 왼쪽(0~i-1)의 수들을 모두 곱하고 거기에 오른쪽(i~length-1) 수들을 모두 곱한 것이 answer[i]가 된다.

따라서 i의 left, right에 맞는 수를 left[i], right[i] 배열에 저장하자.

이는 간단한 for문으로 구할 수 있지만 각 배열을 저장하기 위해 공간 복잡도는 O(n)가 소모된다.

 

이번에는 추가적으로 공간 복잡도를 O(1)로 최적화를 해보자.

사실 left와 right는 바로 정답 배열 answer에 누적 시켜놓으면 굳이 배열로 저장을 할 필요가 없다.

이를 위해 일단 answer에는 left의 값을 저장하고,

right값은 right_prod에 누적시키면서 answer값에 곱해주면 된다.

 

 

간단한 답을 구하는 것에도 시간과 공간 복잡도를 최적화해보는 좋은 문제였다. 

 

코드