[Leetcode 아주 상세한 문제풀이] 238. Product of Array except Self - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 238번 문제 Product of Array except Self 다.

우선 문제를 살펴보자.

 

리트코드 238번 문제 Product of Array except Self (링크)

Product of Array Except Self - LeetCode

Product of Array Except Self - LeetCode

 

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.

Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
 
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30

 

 

문제 설명

문제를 간략히 살펴보자.

정수로 이루어진 배열이 주어지는데, 이때 해당 인덱스에 자신을 제외한 다른 모든 값을 곱한 값으로 대체하라는 것이다.

위의 예제 1번에서 보는 것처럼 첫번째 index에 첫번째 index에 해당하는 값 1을 제외한 나머지 값들 (2, 3, 4)을 모두 곱한 값을 업데이트 하라는것이다.

이 문제는 어렵진 않지만 몇 가지 제한조건이 있다.

우선 배열의 길이는 2 ~ 105 사이여야 하며, 배열 안 정수는 -30 ~ 30 사이여야 한다.

특히 가장 중요한 제한조건은 O (n)의 time complexity를 가져야 한다는 것이다.

또한 나누는 연산 또한 할 수 없다.

이제 문제를 풀어보자.

 

 

문제 접근법

이 문제를 푸는 간단한 방법은 배열 내 모든 숫자를 곱한 다음에,

해당 인덱스에서 그 숫자로 나누기를 해주면 자기 자신을 제외한 모든 다른 수의 곱을 구할 수 있다.

하지만 문제의 조건에 따라 나누기 연산은 할 수 없다.

이 문제를 풀기 위한 한 가지 아이디어는 두 개의 array를 만들어

자기 자신의 왼쪽에 있는 숫자들의 곱과 오른쪽에 있는 숫자들의 곱을 저장한 후

마지막에서 두 array를 곱해 자신을 제외한 다르 모든 수들의 곱을 구할수 있다.

위의 예제에서 처럼 [1, 2, 3, 4] 배열을 생각해 보자.

예를 들어 '3'을 기준으로 왼쪽에 있는 숫자들 (1, 2)의 곱은 첫번째 배열에 넣어두고

'3'을 기준으로 오른쪽에 있는 수자 (4)는 두번째 배열에 넣어둔다.

그리고 이 과정을 배열 내 모든 숫자에 대해  진행한 뒤

첫번째 배열에서 왼쪽에 있는 숫자들의 곱 (1*2)과 두번째 배열에서 오른쪽에 있는 숫자의 곱 (4)을

구하게 되면 결과적으로 '3'을 제외한 모든 숫자들의 곱을 구할 수 있다.

위 예시에서는 각 배열이 다음과 같이 구해진다.

첫번째 배열 = [1, 1, 1*2, 1*2*3] # 해당 인덱스에서 왼쪽에 있는 숫자들의 곱

두번째 배열 = [2*3*4, 2*3, 4, 1]  # 해당 인덱스에서 오른쪽에 있는 숫자들의 곱

 

 

문제 풀이

이제 코드를 한 번 살펴보자.

우선 배열을 입력받을 함수를 지정해 준다 (line 1)

그리고 배열 길이를 확인해 준다 (line 2)

이제 앞서 언급한 두 개의 배열을 채워넣어야 하는데,

첫번째 배열은 해당 인덱스의 왼쪽에 있는 값들의 곱,

두번째 배열을 해당 인덱스의 오른쪽에 있는 값들의 곱을 구해보도록 하자.

이 두개의 배열을 [1]로 초기화를 해준다 (line 5-6) 

그 후 for loop로 첫번째 배열부터 채워 나가는데, (line 10)

첫번째 인덱스는 곱할게 없으므로 1을 넣어주고 (line 9 and 11)

그 다음 인덱스 부터는 이전 인덱스의 값을 곱해준다 (line 12)

이 과정을 두번째 배열에 대해서도 동일하게 진행해준다 (line 15-18)

그리고 첫번째 배열과 두번째 배열을 모두 구한 후 같은 인덱스 값 끼리 곱한다.

위에서 설명했듯 첫번째 배열은 해당 인덱스에서 왼쪽에 있는 값들의 곱

두번째 배열을 해당 인덱스에서 오른쪽에 있는 값들의 곱이기 때문에

이 둘을 곱하면 해당 인덱스를 제외한 모든 값들을 곱한것이 된다. 

 

 

문제 풀이 코드

def productExceptSelf(nums):
    n = len(nums)
    
    # Initialize left and right arrays to store products to the left and right of each element
    left_products = [1] * n
    right_products = [1] * n
    
    # Fill the left_products array
    left_product = 1
    for i in range(n):
        left_products[i] = left_product
        left_product *= nums[i]
    
    print(left_products)
    
    # Fill the right_products array
    right_product = 1
    for i in range(n - 1, -1, -1):
        right_products[i] = right_product
        right_product *= nums[i]
    
    print(right_products)
    
    # Calculate the final answer using left_products and right_products
    answer = [left_products[i] * right_products[i] for i in range(n)]
    
    return answer
 
# Test cases
nums1 = [1, 2, 3, 4]
print(productExceptSelf(nums1))  # Output: [24, 12, 8, 6]
 
#nums2 = [-1, 1, 0, -3, 3]
#print(productExceptSelf(nums2))  # Output: [0, 0, 9, 0, 0]