[파이썬 알고리즘 인터뷰][배열] 자신을 제외한 배열의 곱

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력

 

책에서 구현된 코드

def productExceptSelf(self, nums: 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] = out[i] * p
        p = p * nums[i]
        
    return out

 

기억해야할 기법

• 공간 복잡도를 더 줄이는 방식을 고려
  • 사용할 필요가 없는 공간을 고민할 것

 

내가 구현한 코드

def product_except_self(nums: list[int]) -> list[int]:
    front = [ nums[0] ]
    rear = [ nums[-1] ]
    result = []

    for i in range(1,len(nums)):
        front.append(nums[i] * front[-1])
    for i in range(len(nums)-2, -1, -1):
        rear.append(nums[i] * rear[-1])
    rear = rear[::-1]

    result.append(rear[1])
    for i in range(1,len(nums)-1):
        result.append( front[i-1] * rear[i+1] )
    result.append(front[-2])

    return result

• 속도는 같으나 공간 복잡도에서 큰 차이를 보임
• 책에서 구현한 코드

• 내가 구현한 코드