[Leetcode]238. Product of Array Except Self

1. problem : 

https://leetcode.com/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=leetcode-75

 

2. solution 1 :

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n
        
        # Calculate left products
        left = 1
        for i in range(n):
            result[i] = left
            left *= nums[i]
        
        # Calculate right products and final result
        right = 1
        for i in range(n - 1, -1, -1):
            result[i] *= right
            right *= nums[i]
        
        return result

 

예시, [1,2,3,4,5]이 nums라고 가정하자. 0부터 시작에서 끝으로인 left와 끝에서 시작해서 0으로 순회를 하는 right를 설정한다. 이제 작동방식을 자세히 알아보자. 

 

● 왼쪽부터 순회 : (index 0부터 len(nums)-1까지)

left
index	0	1	2	3	4
nums	1	2	3	4	5
result

 

left	1
index	0	1	2	3	4
nums	1	2	3	4	5
result	1

우선 , 첫 번째 반복문을 보자. i = 0이다 그러면 result [0] = 1이 되고, left값은 1이 된다.

 

left	1*1	1*2
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1

 두 번째다. i = 1이다. 그러면 result [1] = 1이 되고, left값은 1*2인 2가 된다. 

 

left	1*1	1*2	1*2*3
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1	1*2

세 번째다. i = 2다. 그러면 result [2] = 2가 되고, left값은 1*2*3이 된다. 

 

left	1*1	1*2	1*2*3	1*2*3*4
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1	1*2	1*2*3

네 번째다. i=3이다. 그러면 result [3] = 1*2*3이 되고, left값은 1*2*3*4가 된다. 

 

 

left	1*1	1*2	1*2*3	1*2*3*4	1*2*3*4*5
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1	1*2	1*2*3	1*2*3*4

다섯 번째다. i =4이다. 그러면 result [4] = 1*2*3*4가 되고, left값은 1*2*3*4*5 된다. 

 

● 오른쪽부터 순회 : (index len(nums)-1, 0까지) 

right
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1	1*2	1*2*3	1*2*3*4

 

right					1*5
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1	1*2	1*2*3	1*2*3*4*1

첫 번째다.  i = 4일 때다.  그러면 result [4] = 1*2*3*1이 된다. right 값은 1*5가 된다. 

 

right				5*4	1*5
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1	1*2	1*2*3*1*5	1*2*3*4*1

두 번째다. i = 3일 때다. 그러면 result [3] = 1*2*3*1*5가 된다. right 값은 1*4*5가 된다. 

 

right			5*4*3	5*4	1*5
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*1	1*2*4*5	1*2*3*1*5	1*2*3*4*1

세 번째다. i =2일 때다. 그러면 result [2] = 1*2*1*4*5가 된다. right값은 4*5*3이 된다.  

 

right		5*4*3*2	5*4*3	5*4	1*5
index	0	1	2	3	4
nums	1	2	3	4	5
result	1	1*3*4*5	1*2*4*5	1*2*3*5	1*2*3*4

네 번째다. i =1일 때다. 그러면 result [1] = 1*3*4*5가 된다. right값은 5*4*3*2가 된다. 

 

right	5*4*3*2*1	5*4*3*2	5*4*3	5*4	1*5
index	0	1	2	3	4
nums	1	2	3	4	5
result	2*3*4*5	1*3*4*5	1*2*4*5	1*2*3*5	1*2*3*4

다섯 번째다. i =0일 때다.  그러면 result [0] = 2*3*4*5가 되고, right값은 5*4*3*2*1이 된다.  

 

결괏값은 result를 return 한다. 

 

결론 : result값에 현재 인덱스 전까지 곱하기 결과를 대입하고, left or right에 자기 인덱스의 값을 곱해서 갱신한다. 즉, index 한 개만큼의 차이를 두어, 진행한다는 것이다. left와 right도 마찬가지.. 

 

3. solution 2 :

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        zero_count = 0 
        multi_value = 1 
        ans = [-1] * len(nums)
        for num in nums:
            if num == 0:
                zero_count += 1 
                continue 
            else:
                multi_value *= num 
        
        for i in range(len(nums)):
            if nums[i] == 0 and zero_count-1 > 0:
                ans[i] = 0
            elif nums[i] == 0:
                ans[i] = multi_value 
            elif zero_count > 0:
                ans[i] = 0 
            else:
                ans[i] = int(multi_value/nums[i]) 
        return ans

이 solution은 zero를 카운트해서, zero_count에 저장한다. 그리고 multi_value라는 변수를 두어, list의 곱셈 결과를 저장한다. 곱셈 결과를 저장할 때는 0이 있다면 곱하지 않는다. 왜냐하면, zero_count라는 변수가 있기 때문에, zero_count가 양수라면 결과를 출력할 때, 0으로 출력하면 되기 때문이다. 그 외의 경우는 자기 자신으로 나누어서 결과를 출력한다. 

 

이 solution은 그저 참고용이다.