[leetcode][238] Product of Array Except Self

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

---

1보다 큰 양수들의 배열이 주어질 때

output[i] = nums[i] 를 제외한 나머지 nums 요소들의 곱

인 output 배열을 구하라.

단, 나누기는 쓰지말고 출력배열을 제외하고는 추가 메모리를 사용하지 말아라.

---

n = nums 배열 크기라 하자.

output[i] = nums[0] ~ nums[i-1] 의 곱. => nums를 앞에서부터 탐색하면서 output[i] = output[i-1] * nums[i-1]

nums[i] = nums[i] ~ nums[n-1] 의 곱. => nums를 뒤에서부터 탐색하면서 nums[i] = nums[i] * nums[i+1]

output[i] = output[i] * nums[i+1] = (nums[0] ~ nums[i-1]의 곱) * (nums[i+1] ~ nums[n-1]의 곱)  = 정답

 

시간복잡도는 O(n)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/238.%20Product%20of%20Array%20Except%20Self.cpp