728x90
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
division 연산 없이 O(n)의 시간 복잡도로 계산하라고 제약 조건이 주어진 문제였다!
풀이
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [1] * n
for i in range(n):
if i == 0:
left[i] = nums[i]
else:
left[i] = (left[i-1] * nums[i])
right = [1] * n
for i in range(n-1, -1, -1):
if i == n-1:
right[i] = nums[i]
else:
right[i] = (right[i+1] * nums[i])
answer = [1] * n
for i in range(n):
if i == 0:
answer[i] = right[i+1]
elif i == n - 1:
answer[i] = left[i-1]
else:
answer[i] = (left[i-1] * right[i+1])
return answer
왼쪽과 오른쪽의 누적합을 계산하고 출력하는 방식을 떠올렸다.
통과한 코드지만, 인덱스 하나하나 생각하며 풀다보니 불필요한 조건문이 많아졌다.
range를 약간 수정하면 불필요한 조건문을 제거하여 아래와 같이 작성할 수 있다.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [1] * n
for i in range(1, n):
left[i] = left[i-1] * nums[i-1]
right = [1] * n
for i in range(n-2, -1, -1):
right[i] = right[i+1] * nums[i+1]
answer = [1] * n
for i in range(n):
answer[i] = left[i] * right[i]
return answer
참고로 이러한 문제에서 왼쪽 누적곱을 prefix product, 오른쪽 누적곱을 suffix product로 자주 지칭한다.
728x90
