“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/product-of-array-except-self/
“배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.”는 문제이다.
[1,2,3,4]가 입력인 경우, [24,12,8,6]이 정답이 된다. 여기서 골치 아픈 점은 You must write an algorithm that runs in O(n) time and without using the division operation.” -> “나눗셈 안 쓰고 O(n)에 풀이할 것”이다. O(n^2)에 풀자면 간단히 해결되고, 나눗셈을 쓸 수 있으면 배열의 전체 요소의 곱을 구해두고 nums[i]를 나누면 답이 나오기 때문이다.
오늘도 바로 풀이 방법이 떠오르지 않아서 풀이를 참고 했다.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
p = 1
out = []
for i in range(len(nums)):
out.append(p)
p = p * nums[i]
p = 1
for i in range(len(nums)-1,-1,-1):
out[i] = out[i] * p
p = p * nums[i]
return out- 인덱스를 기준으로 왼쪽 요소들을 모두 곱한 값을 output[i]에 저장한다.
- 인덱스를 기준으로 오른쪽 요소들을 모두 곱한 값을 output[i]와 곱해서 output[i]에 저장한다.
p라는 확장?을 생각할 수 있어야 한다.