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

github.com/onlybooks/algorithm-interview

졸리당.....이거만하구 자야지 

---

238. Product of Array Except Self

 

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

 

---

Product of Array Except Self - LeetCode

 

 

본 문제에 제약조건이 존재한다. Note: Please solve it without division and in O(n).

 

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

 

for문을 2번 사용한다.

 1) 왼쪽으로 이동하면서 곱을하고 

 2) 오른쪽으로 이동하면서 곱을 한다.

나를 제외한 양 옆의 이웃들을 만나게 해주는 것

 

책에 있는 그림을 보고 한참을 이게 뭐지했다. 으이구 멍청하긴... 이해력이 이렇게 안좋아서야..!

난 그냥 코드로 보는게 훨씬 이해하기 편하다. 

 

onlybooks/algorithm-interview

 

나 이문제 3달전에 풀었었다.

from functools import reduce
from collections import Counter

# 이중 for문으로 풀 수 있겠지만 O(n)으로 풀어야 함
class Solution:
    def multiply(self,arr):
        return reduce(lambda x, y: x * y, arr)

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # 0의 개수를 체크 
        counterForZero = Counter(nums)[0]
        
        # 0 이 1개라면 0이 선택되는 경우 빼고 다 0이고 0의 자리에만 product value
        if counterForZero == 1:
            res = [0]*len(nums)
            idx = nums.index(0)
            res[idx] = self.multiply(nums[:idx]+nums[idx+1:])
            return res
    
        #0이 1개 이상이면 언제든 0
        if counterForZero  > 1:
            return [0]*len(nums)
        
        #0이 하나도 없는 경우
        res = self.multiply(nums)
        for idx,num in enumerate(nums):
            nums[idx] = int(res/num)
        
        return nums 

 

확실히 책에서 제시한 방식이 훨씬 깔끔하고 보기좋다. 이래서 공부를 해야한다.