[LeetCode]Product of Array Except Self

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

nums 배열이 주어지면 자신을 제외한 숫자들의 곱을 구하는 문제입니다. 단, 나눗셈 연산은 금지되어 있습니다.

 

처음 시도한 답안

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        nums_len = len(nums)
        
        left = [1] * nums_len # 본인 왼쪽 숫자들을 곱한 값들
        right = [1] * nums_len # 본인 오른쪽 숫자들을 곱한 값들

        for i in range(1, nums_len):
            left[i] = left[i-1] * nums[i-1] # 왼쪽에 위치한 값을 누적시키면서 곱하기

        for j in range(nums_len-2, -1, -1):
            right[j] = right[j+1] * nums[j+1] # 오른쪽에 위치한 값을 누적시키면서 곱하기

        answer = []
        for i in range(nums_len):
            answer.append(left[i] * right[i]) # 본인기준 왼쪽과 오른쪽을 곱해서 정답 구하기 
            
        return answer

# nums = [1,2,3,4]
# after_left = [1,1,2,6]
# after_right = [24,12,4,1]
# after_left * after_right = [24,12,8,6]

접근 방법

1. 본인을 제외한 왼쪽 숫자들의 곱한 값을 left에, 오른쪽 숫자들의 곱한 값을 right에 기록합니다.
2. 왼쪽에 위치한 값을 누적시키면서 곱셈을 통해 left 값을 기록합니다.
3. 오른쪽에 위치한 값을 누적시키면서 곱셈을 통해 right 값을 기록합니다.
4. left와 right와의 곱셈을 통해 본인을 제외한 숫자들의 곱을 구합니다.

가장 이해하기 쉽고 직관적이지만, 문제에서 정답 배열을 제외하고 O(1) 공간 복잡도에 대한 제약이 있어서 최적화가 필요했습니다.

 

두번째로 시도한 답안 - 공간 복잡도 최적화

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        nums_len = len(nums)
        
        answer = [1] * nums_len # 정답 배열 1개만을 사용합니다. Space: O(1)

        for i in range(1, nums_len):
            answer[i] = answer[i-1] * nums[i-1] # 왼쪽에 위치한 값을 누적시키면서 곱하기

        right = nums[-1] # 오른쪽에 대한 값은 right 변수로 누적시키면서 곱하기 
        for j in range(nums_len-2, -1, -1): # 오른쪽부터 왼쪽으로 순회
            answer[j] = answer[j] * right # left값(answer[j])과 right값을 곱하기
            right = right * nums[j] # right값을 곱하기 누적하면서 갱신

        return answer

접근 방법

1. 첫번째 방법과 비교해서 answer 배열 1개만 사용하여 O(1) 공간복잡도 제약을 맞춥니다.
2. 동일하게 왼쪽에 위치한 값을 누적시키면서 곱하고 answer 배열에 반영합니다.
3. right값을 nums의 가장 마지막 값으로 초기화하고 해당 변수에 오른쪽 값들을 누적시키면서 곱하는 용도로 사용합니다.
4. left값과 right값을 곱하고 answer 배열에 반영합니다.
5. right값의 누적 곱셈을 위해 nums[j]와 right를 곱해 값을 갱신합니다.

나눗셈 연산을 활용하면 쉽게 풀이할 수 있지만 문제의 제약조건으로 인해 풀이 방법을 찾는 것이 어려웠습니다. 자신의 값을 제외해야 하므로 왼쪽과 오른쪽의 누적 곱셈값을 따로 구해 곱하는 것이 가장 큰 아이디어인 것 같습니다.