[배열] Product of Array Except Self

Product of Array Except Self - LeetCode

def multi(k: list):
    tot = k.pop()
    while k:
        v = k.pop()
        tot *= v
    return tot
 
def productExceptSelf(nums: list[int]):
    ans = []
    d = dict()
 
    # [15] 일 경우 바로 15 리턴
    if len(nums) == 1 or len(nums) == 0:
        return nums
 
    # 첫 항을 제외한 곱의 값 계산
    ans.append(multi(nums[1:]))
 
    # list(nums) 이 3이상일 때부터 아래 for 문 작동 (range(1,-1) range(1,0) range(1,1) xx)
    # [1] 부터 [-2] 까지
    for i in range(1, len(nums) - 1):
        # 없으면 시간 초과: dict 를 사용하여 중복된 key 일 경우 메모제이션 된 값 사용 (dict 사용법: dict 에 값을 저장 할 때, containment 로 찾을 키워드를 key 로 잡는다)
        if nums[i] in d:
            ans.append(d[nums[i]])
            continue
 
        val = multi(nums[:i] + nums[i + 1:])
        ans.append(val)
        d[nums[i]] = val
 
    # 마지막 항을 제외한 곱의 값 계산
    ans.append(multi(nums[:-1]))
    return ans
 
 
nums = [1, 2, 3, 4]
print(productExceptSelf(nums))

---

 dict 를 사용해서 값의 중복을 체크하는 작업이 필요하다고 생각하면, dict 에 값을 추가 할 때 key 부분에 containment 작업을 통해 찾을 속성을 저장한다. 왜냐하면 dict 의 경우 if target in d 를 수행할 때 시간복잡도가 O(1)이기 때문에 list 에서 찾는 작업에 비해 시간복잡도에서 큰 장점을 가지기 때문이다.