리트코드(LeetCode) 238번 자신을 제외한 배열의 곱(Product of Array Except Self)

---

 

 

📌  첫 번째 풀이 (시간 초과)

우선 제일 먼저 생각난 것은 for문을 돌리면서 자신을 제외한 모든 수를 곱한 것을 새로운 arr배열에 넣는 것이었다.

하지만 이를 위해서는 필수적으로 이중 for문이 들어가게 되고 문제의 조건인 시간 복잡도 O(N)을 만족할 수 없게 되어

시간 초과가 나오게 되었다.

 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        arr = []
        for i in range(len(nums)):
            num = 1
            for j in range(len(nums)):
                if i == j:
                    continue
                else:
                    num *= nums[j]
            arr.append(num)
        return arr

 

 

 

 

 

📌  두 번째 풀이

그렇다면 어떻게 이중 for문 즉 O(N^2)이 아닌 O(N)에 풀 수 있을까?

방법은 자기 자신을 제외하고 왼쪽의 모든 곱과 오른쪽의 모든 곱을 구해 그 둘을 곱하는 것이다.

 

 

우선 왼쪽에 있는 모든 곱을 out이라는 리스트에 넣어보자

코드는 다음과 같다.

 

out = []
p = 1
for i in range(0, len(nums)):
    out.append(p)
    p = p * nums[i]

 

 

여기서 중요한 점은 새롭게 p를 갱신해 주는 부분 앞에 out.append를 넣어 주어 첫 번째 값 곱셈은 항상 1이며 마지막 값 곱셈을 항상 제외하여 주는 것이다.

 

 

이제 오른쪽에 있는 곱은 기존에 있는 out(왼쪽에 있는 곱이 들어간 리스트)에 곱해주자

코드는 다음과 같다.

 

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

 

우선 P를 다시 1로 초기화해주고 for문을 첫 번째를 len(nums) - 1에서 시작해 0까지 (-1의 전) -1씩 내려가는 반복문을 돌려 기존의 out배열의 i번째와 곱해준다.

 

 

 

이를 이해하기 쉽게 그림으로 나타내면 다음과 같다.

 

 

 

nums = [1, 2, 3, 4]

 

 

 

 

nums = [-1, 1, 0, -3, 3]

 

 

 

 

 

최종 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        # 왼쪽 곱셈
        for i in range(0, len(nums)):
            out.append(p)
            p = p * nums[i]

        p = 1
        # 오른쪽 곱셈
        for i in range(len(nums)-1, -1, -1):
            out[i] *= p
            p *= nums[i]
        return out