[TAVE/파이썬 알고리즘] Ch7 | 배열 - 11번 자신을 제외한 배열의 곱

왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

1️⃣왼쪽→오른쪽 방향으로 곱한다.

    out = []

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

📌공간 복잡도는 O(1)을 위해 기존 out 변수를 재활용한다.

👉🏻p와 리스트의 각 요소들 간의 곱셈 결과를 그대로 out 리스트에 담는다.

👉🏻결과: [1, 1, 2, 6]

✍🏻만약 별도의 리스트 변수를 만들고 그 변수에 우측 곱셈 결과를 넣으면 공간 복잡도는 O(1)이 된다.

 

✅공간복잡도 O(n)

👉🏻저장되는 메모리, 변수 양에 따라서 공간복잡도가 결정된다. 배열이 중첩될수록 n의 차수가 높아진다.

✍🏻참고로 시간복잡도는 코드 실행의 시간에 따라 결정된다. for문이 중첩될수록 n의 차수가 높아진다.

 

 

2️⃣왼쪽 곱셈 결과에 오른쪽 마지막 값부터 곱한다.

    p = 1
    #왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
    for i in range(len(nums) -1, 0-1, -1):
        out[i] = out[i] * p
        p = p * nums[i]

👉🏻out에 들은 곱셈 결과에 nums의 맨 마지막 요소부터 차례로 곱한다.

👉🏻결과: [24, 12, 8, 6]

✍🏻range(x, y, z): 여기서 세 번째 파라미터인 z는 증분을 지정한다. 여기서는 -1이므로 인덱스가 1씩 줄어든다.

def productExcepSelf(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, 0-1, -1):
        out[i] = out[i] * p
        p = p * nums[i]
    return out

📌전체코드