[LeetCode] #238. Product of Array Except Self (Python/파이썬)

등급: Medium

📖Problem: 238. Product of Array Except Self

정수 배열 nums가 주어지면, answer[i]가 nums[i]를 제외한 nums의 모든 요소의 곱과 동일하도록 배열 answer을 반환한다.
nums의 접두어나 접미어의 곱은 32비트 정수에 맞도록 보장된다. (따라서 메모리는 걱정하지 않아도 된다)
단, 나누기 연산을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 한다.

🔍Institution

나누기 연산을 사용하면 안 되고 시간복잡도가 O(n)이 되도록 해야 한다.
1차 반복문 사용을 하여 짠 코드는 아래와 같다. 시간복잡도가 (O(n^2)이므로, 테스트케이스가 통과하더라도, 시간초과가 발생하게 된다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        answer = []
        point = 0

        while point < len(nums):
            product = 1
            for i in range(len(nums)):
                if i == point:
                    pass
                else:
                    product *= nums[i]
            answer.append(product)
            point += 1

        return answer

즉, 시간초과를 줄이기 위해서는

반복문을 따로 쓰고, 메모리 사용을 더 늘리는 방식을 써야 한다.

따라서 반환해야 하는 answer리스트 이외에, 리스트 2개(pre와 post리스트)를 추가로 만든다. 그리고 각각 따로 반복문을 돌리면서 pre와 post리스트에 값을 저장한 후, 이 값을 이용해 answer리스트에 값을 저장한다.

pre리스트에 pre[i]에 nums[i]와 그 이전의 값들을 곱한 값들이 저장된다.
post리스트는 post[i]에 nums[i]와 그 이후의 값들을 곱한 값들을 모두 저장한다.

동작 과정은 아래에서 살펴보겠다.

🔍Approach

pre리스트에 pre[i]에 nums[i]와 그 이전의 값들을 곱한 값들이 저장된다.

post리스트는 post[i]에 nums[i]와 그 이후의 값들을 곱한 값들을 모두 저장한다.

다 구하면 아래와 같이 정리해볼 수 있겠다.

pre와 post를 이용해서 answer에 값을 저장해야 한다. 그 전에 “인간적”으로 answer에 원래 저장되어야 하는 값들은 i에 해당하는 값을 제외한 나머지 값들을 곱해야 하므로 위의 빨간색 글씨처럼 저장되어야 한다.
pre와 post를 활용해서 할 수 없을까?
모든 i에 대해 한번에 규칙이 해당하지 않는 것 같으니 i = 0일 때부터, pre와 post와 값이 똑같은 것을 찾아보도록 한다.

i=0일 때,

i = 0일때는 2*3*4가 똑같이 들어와야 한다. 이와 똑같은 값은 post[1]에 있는 값이다. 이때 post[0]과 pre[3]도 해당하는 거 아니냐고 생각할 수도 있지만, nums[0]값이 1이 아니라 다른 값이 들어오게 되면 값이 바뀌게 되므로 해당사항이 없다.

따라서 i=0일때, answer[i] = post[i+1]이다.

i가 마지막번째일 때,

i가 마지막일때는 123이 똑같이 들어와야 한다. 이와 똑같은 값은 pre[2]에 있는 값이다. 이를 일반화시키면 아래와 같다.

i = len(nums-1)일때, answer[i] = pre[i-1]

i = 1 or i = 2일 때,

먼저 i = 1일 때, 1*3*4가 되어야 한다. 이 값이 똑같이 되도록 하려면 pre[0]과 post[2]의 값이 들어가야 한다.

i = 2일 때는 1*2*4가 되어야 한다. 이 값과 똑같이 하려면 pre[1]과 post[3]의 값이 들어가야 한다.

이를 통해 일반화시키면 아래와 같다.

i가 그 외일때,
answer[i] = pre[i-1] * post[i+1]

이렇게 규칙성을 발견하였으니, flow를 작성하고 코드를 작성해보도록 한다.

📌Flow

2개의 리스트(pre, post)를 만들어서 값을 0으로 저장한다. 이 값들에 for문을 통해 값을 저장하고, 이후 그 값들을 이용해 answer 리스트에 값을 채운다.
pre리스트에 pre[i]에 nums[i]와 그 이전의 값들을 곱한 값들이 저장된다.
post리스트는 post[i]에 nums[i]와 그 이후의 값들을 곱한 값들을 모두 저장한다.
이후, 규칙에 따라 앞부분, 뒷부분, 중간 부분에 해당하는 값들을 answer에 저장한다.
- i가 0일 때 → answer[i]에 post[i+1]의 값을 저장한다.
- i가 리스트의 길이일 때 → answer[i]에 pre[i-1]의 값을 저장한다.
- i가 중간에 있는 값일 때 → answer[i]에 pre[i-1] * post[i+1]의 값을 저장한다.
이후 answer리스트를 반환한다.

🚨주의!

pre=post=answer = [0] * len(nums)

이렇게 코딩 짰는데 pre랑 post가 연동이 되어버리는 현상이 발생..!!
오늘 처음 알게 되었는데 파이썬의 “리스트”는 C언어의 “포인터”의 개념과 같아서 이런 경우가 발생할 수도 있다고 한다.
따라서 리스트를 모두 따로 선언해주었다.

pre = [0] * (len(nums))
post = [0] * (len(nums))
answer = [0] * (len(nums))

🚩My submission

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        pre = [0] * (len(nums))
        post = [0] * (len(nums))
        answer = [0] * (len(nums)) 
        ans = 1

        for i in range(len(nums)):
            ans *= nums[i]
            pre[i] += ans

        ans = 1
        for i in range(len(nums)-1, -1, -1):
            ans *= nums[i]
            post[i] += ans

        for i in range(len(nums)):
            if i == 0:
                answer[i] = post[i+1]
            elif i == (len(nums)-1):
                answer[i] = pre[i-1]
            else:
                answer[i] = pre[i-1] * post[i+1]

        return answer

🚩Others submission

리트코드 상위권에 있던 답안:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        products = [1] * length
        for i in range(1, length):
            products[i] = products[i-1] * nums[i-1]

        right = nums[-1]
        for i in range(length-2, -1, -1):
            products[i] *= right
            right *= nums[i]

        return products

JB 선배 답안:

class Solution:
   def productExceptSelf(self, nums: List[int]) -> List[int]:
       lanswer = [1] * len(nums)
       ranswer = [1] * len(nums)
       answer = [1] * len(nums)

       temp = 1
       for i in range(len(nums)):
           temp *= nums[i]
           lanswer[i] = temp

       temp = 1
       for i in range(len(nums)-1, -1, -1):
           temp *= nums[i]
           ranswer[i] = temp

       for i in range(len(nums)):
           if i == 0:
               answer[i] = 1 * ranswer[i+1]
           elif i == (len(nums)-1):
               answer[i] = 1 * lanswer[i-1]
           else:
               answer[i] = lanswer[i-1] * ranswer[i+1]

       return answer

💡TIL

이 문제는 페이스북에서 낸 문제라고 한다.
다른 자료구조가 쓰이는 문제가 아니라 오로지 “아이디어”로 푸는 무제라 그런지, 해당 아이디어까지 생각해내기가 무척 어려웠다. 이런 패턴을 학습했으니, 앞으로 문제 푸는 폭이 더 넓어질 거라고 생각한다.
또한, 시간복잡도와 공간복잡도는 trace-off 관계이기 때문에 시간복잡도가 높아지면 공간복잡도가 줄어들고, 시간복잡도가 줄어들면 공간복잡도가 늘어난다는 특징이 있다. 이 특징을 이용해서 시간복잡도를 줄일 때, [1. 이중 반복문이 아닌 반복문을 낱개로 따로 사용한다.] [2. 공간복잡도를 늘린다.]라는 아이디어를 떠오릴 수 있다는 것을 알게 되었다.
규칙을 찾을 때 모든 것에 다 적용되는 규칙을 먼저 찾기보다는 하나하나 찾아보면서 경우의 수를 나눠보도록 하자!

저작자표시 비영리 변경금지

minggu