leecode 238. Product of Array Except Self 풀이

문제 : int 로 이루어진 list가 주어질 때 해당 인덱스의 원소를 제외한 나머지 원소의 곱을 인덱스와 원소로 가지는 list는 반환하라

Follow up :

 

아이디어 : K * O(n) 의 시간 복잡도를 가지기 위해, 0을 제외한 나머지 모든 원소의 곱을 곱해서 저장한다. 0은 갯수를 카운트 한다. 다음 번 순회에서 0일때는 다른 0이 있는 지 확인 후 있으면 0 반환, 없으면 m을 반환. 0이 아닐때는 0이 있다면 0 반환, 없으면 m // num을 반환한다.

 

코드 :

 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        m = 1
        zc = 0
        ans = []
        for num in nums:
            if num == 0:
                zc += 1
            else:
                m *= num
        for num in nums:
            if num == 0:
                if 1 < zc:
                    ans.append(0)
                else:
                    ans.append(m)
            else:
                if 0 < zc:
                    ans.append(0)
                else:
                    ans.append(m//num)
        return ans

 

학습 포인트 : 문제를 풀기 위한 최적화된 알고리즘을 생각하며 시간복잡도와 메모리복잡도를 함께 고려해서 생각하면 쉽게 문제를 풀 수 있다.

 

출처 : leetcode.com/problems/product-of-array-except-self/