Leet code 238 - Product of Array Except Self

 

시간 복잡도로 O(N) 공간복잡도로 O(1) 제약 조건이 걸려있다.

product 는 곱의 영어 표현으로써 더 일반적이라고 한다.

배열안에서, 해당 인덱스의 num 값만 곱해지지 않은 값을 리스트에 넣고, 그 리스트를 반환해야 하는 문제이다.

 

---

 

나의 풀이

 

실제 그 리스트를 조작하거나 해당 요소를 제거하고 곱하는 방식으로 결과값을 구하면 어떨까 생각을 해보았으나,

해당 값이 하나가 아니라, 지속적으로 구해 새 리스트에 넣어줘야하기 때문에, 리스트 조작보다는,

전체의 곱을 구하고, 해당 인덱스 값만 나눠서 결과값을 구하는 방식을 생각했다.

 

하지만 배열에 0이 있다면 어떨까?

일단 해당 인덱스 값만 나눠서 반환한다는 발상이, 0으로는 나눌 수 없기에 역서 문제의 난점이 생겼다.

 

이를 조건 문으로 처리해줬다.

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        ls1 = []

        cnt = 0
        ans = 1

        for i in nums:
            if i == 0 and cnt == 0:
                cnt += 1
                ans *= 1

            elif i == 0 and cnt > 1:
                ans = 0
                cnt += 1
                break

            else:
                ans *= i
        

                    
        for i in nums:
            
            if i == 0 and cnt == 1:
                ls1.append(ans)
            elif cnt > 0:
                ls1.append(0)
            elif i == 0:
                ls1.append(ans)
            else:
                ls1.append(ans / i)
            
        return ls1

전체 곱을 구할때 0이 있는경우 0대신 1을 곱해서,  0을 제외한 전체 곱을 구할 수 있었다. 

다만 조건문을 통해서 0이 한개 이상 보이는 경우에는 ans를 0으로 초기화 해주었다.

 

0이 하나 밖에 없는 경우에는 nums값이 0인 인덱스만 0을 제외한 값을 넣고 나머지는 0을 넣어줘야한다.

그외 모든 경우에서 cnt가 0이상인 경우에는 모두 0을 넣어줘야한다.

그다음 경우에는 ans에서 그 값을 나눈 값을 넣어준다.

i가 0 인 경우에 ans을 넣어준다( 사실 cnt가 1일때만 ans가 0이 아니니 그냥 0을 넣는 것과 같음.

나머지 경우에는  일반적인 경우로 ans에 대해  해당 인덱스값을 나눈 값을 넣어준다.

 

---

뭔가 풀이를하면서 시원한 풀이는 아니라는 생각이 들었다. 또한 공간복잡도와 시간복잡도를 유념하며 풀지도 않았다.

다른 사람들은 어떻게 풀었을까?

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []
        
        acc = 1
        for n in nums:
            res.append(acc)
            acc *= n

        acc = 1
        for i in reversed(range(len(nums))):
            res[i] *= acc
            acc *= nums[i]
            
        return res

뭔가 전혀 다른 발상이다. nums배열을 오른쪽 방향으로 한번, 왼쪽방향으로 한번 두번 순회한다.

오른쪽으로 순회할때는, 0에 해당하는 인덱스를 만나기전까지는 해당 인덱스의 값을 누적곱이 있다가, 그 뒤로 전부 0이 될 것이고,

왼쪽으로 다시한번 순회할때는  해당 인덱스를 제외한 역순 누적곱이  있다가 그뒤로 0이 될 것이다.

 

직관 적으로 이해하기 어려운데, 어쨋든 오른쪽으로 순회하든 왼쪽으로 순회하든 해당 인덱스 값은 곱해지지 않고, 제외 한 값만 곱해진다. 

 

1, 1 , 1x2, 1x2x3

1x2x3x1, 1x2x4,1x4x3,

 

[1,2,3,4]

1 1 2 6

 

이런 풀이 어떻게 생각해내는지 신기하다..