숫자로 이루어진 리스트 nums가 주어졌을 때, 새로운 리스트를 만들어야 합니다. 새 리스트의 각 인덱스 i에 해당하는 값은 원본 리스트에서 인덱스 i의 요소 하나를 제외한 나머지 모든 숫자의 곱입니다. 단, 이 문제는 나눗셈을 사용하지 않고 풀어야 한다는 조건이 있습니다.
예를 들어 입력이 nums = [2, 3, 4, 5, 6]이라면 출력은 [360, 240, 180, 144, 120]이 됩니다. 각 위치의 값은 해당 요소를 제외한 나머지 숫자들을 모두 곱한 결과입니다.
문제 해결 접근 방법
나눗셈 없이 이 문제를 해결하려면 왼쪽 누적 곱(left)과 오른쪽 누적 곱(right), 두 개의 보조 배열을 활용하는 것이 핵심입니다. 각 인덱스 i에 대해 left 배열에는 i보다 앞에 있는 요소들의 곱을, right 배열에는 i보다 뒤에 있는 요소들의 곱을 저장합니다. 최종 결과는 같은 인덱스끼리 두 배열의 값을 곱하면 얻을 수 있습니다.
알고리즘 단계
- nums의 크기가 1 미만이면 그대로 반환합니다.
- l := nums의 크기
- left와 right: 크기가 l인 리스트를 생성하고 초기값은 null로 설정합니다.
- temp := 1로 초기화합니다.
- i를 0부터 nums의 크기까지 반복하며:
- i가 0이면 left[i] := temp
- 그렇지 않으면 temp := temp * nums[i-1] 후 left[i] := temp
- temp를 다시 1로 초기화합니다.
- i를 nums의 크기 - 1부터 0까지 감소시키며 반복:
- i가 마지막 인덱스면 right[i] := temp
- 그렇지 않으면 temp := temp * nums[i+1] 후 right[i] := temp
- 모든 i에 대해 left[i] := left[i] * right[i]로 갱신합니다.
- left를 반환합니다.
구현 예제
class Solution:
def solve(self, nums):
if len(nums) < 1:
return nums
l = len(nums)
left = [None] * l
right = [None] * l
temp = 1
for i in range(len(nums)):
if i == 0:
left[i] = temp
else:
temp = temp * nums[i - 1]
left[i] = temp
temp = 1
for i in range(len(nums) - 1, -1, -1):
if i == len(nums) - 1:
right[i] = temp
else:
temp = temp * nums[i + 1]
right[i] = temp
for i in range(len(nums)):
left[i] = left[i] * right[i]
return left
ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))입력
[2, 3, 4, 5, 6]
출력
[360, 240, 180, 144, 120]
복잡도 분석
이 알고리즘은 세 번의 선형 순회만 수행하므로 시간 복잡도는 O(n)입니다. left와 right 두 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 전체 곱을 나누는 방식과 달리 리스트에 0이 포함되어 있어도 정확하게 동작한다는 장점이 있습니다.