길이가 n(n > 1)인 정수 배열 nums가 주어졌다고 가정해 봅시다. 이때 output[i]가 nums[i]를 제외한 나머지 모든 원소들의 곱과 같도록 하는 배열 output을 구하는 것이 목표입니다. 예를 들어 입력 배열이 [1,2,3,4]라면 결과는 [24,12,8,6]이 됩니다. 중요한 제약 조건은 나눗셈 연산자를 사용하지 않고 문제를 해결해야 한다는 점입니다.
문제 해결 접근 방식
나눗셈 없이 이 문제를 풀려면 각 위치를 기준으로 왼쪽 원소들의 곱(접두사 곱)과 오른쪽 원소들의 곱(접미사 곱)을 활용하면 됩니다. 핵심 아이디어는 다음과 같습니다.
output[i] = (nums[0] × ... × nums[i−1]) × (nums[i+1] × ... × nums[n−1])
알고리즘 단계
right_mul: nums와 같은 크기의 배열을 만들고 0으로 초기화합니다.right_mul의 마지막 원소에 nums의 마지막 원소를 저장합니다.- i를 1부터 nums의 길이까지 반복하며 다음을 수행합니다.
- right_mul[len(nums) − i − 1] = right_mul[len(nums) − i] × nums[len(nums) − i − 1]
output: nums와 같은 크기의 배열을 만들고 0으로 초기화합니다.prefix:= 1,index:= 0으로 설정합니다.- index < len(output) − 1인 동안 반복합니다.
- output[index] = prefix × right_mul[index + 1]
- prefix = prefix × nums[index]
- index를 1 증가시킵니다.
- output의 마지막 원소에 prefix를 저장합니다.
- output을 반환합니다.
파이썬 구현 예제
class Solution(object):
def productExceptSelf(self, nums):
right_multiply = [0] * len(nums)
right_multiply[-1]=nums[-1]
for i in range(1,len(nums)):
right_multiply[len(nums)-i-1] = right_multiply[len(nums)-i] * nums[len(nums)-i-1]
output = [0]*len(nums)
prefix = 1
current_index = 0
while current_index < len(output)-1:
output[current_index] = prefix * right_multiply[current_index+1]
prefix *= nums[current_index]
current_index +=1
output[-1] = prefix
return output
ob1 = Solution()
print(ob1.productExceptSelf([1,3,5,7,9]))
입력
[1,3,5,7,9]
출력
[945, 315, 189, 135, 105]
동작 원리 설명
right_multiply 배열에는 각 인덱스를 기준으로 오른쪽에 있는 모든 원소들의 누적 곱이 저장됩니다. 그다음 왼쪽에서부터 순회하면서 prefix 변수에 현재 위치까지의 왼쪽 원소들의 곱을 유지하고, 이를 오른쪽 누적 곱과 곱해 최종 결과를 만듭니다. 이 방식을 사용하면 나눗셈 없이도 O(n)의 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다.