[LeetCode] CodeTestcaseTestcaseTest Result1352. Product of the Last K Numbers (Python)

Problem

 

Solution

list

list에서 마지막 K개 원소의 총 곱을 구하는 문제.

시간복잡도가 O(N)이면 time out이 발생해서 O(1)으로 해결해야되는 문제!

prefix 곱을 모두 구한 뒤, prefix[n-1] // prefix[n-k-1] 로 뒤에서 k개 원소의 곱을 구한다.

여기서 문제는 분모가 0이되면 안된다.

1) 모든 원소를 저장한 arr중 마지막 k개 원소만 담은 arr[-k:]  에 0이 포함되어있는지 체크
2) k == len(arr[-k:]) 이면 prefix[-1] 마지막 값 반환

3) 분모가 0이면 for문으로 직접 모두 계산

 

Code

class ProductOfNumbers:
    def __init__(self):
        self.prefix = []
        self.val = 1
        self.arr = []

    def add(self, num: int) -> None:
        self.arr.append(num)
        self.val *= num
        self.prefix.append(self.val)

    def getProduct(self, k: int) -> int:
        last_arr = self.arr[-k:]

        if 0 in last_arr:
            return 0
        n = len(self.prefix)
        if k == n:
            return self.prefix[-1]
       
        if self.prefix[n-k-1] == 0:
            answer = 1
            for num in last_arr:
                answer *= num
            return answer
        
        return self.prefix[n-1] // self.prefix[n-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

 

Complexity

Time Complexity

마지막 k개의 곱 구할 경우 0이 포함되어있지 않은 경우 -> 나눗셈으로 한번에 계산 -> O(1)

0이 존재하면 직접 for 문으로 구함 -> O(n)

 

Space Complexity

prefix 배열 저장 -> O(N)

 

 

아래는 다른 사람 풀이!

lass ProductOfNumbers:

    def __init__(self):
        self.pre_mul = []
        self.product = 1
        
    def add(self, num: int) -> None:
        if num is not 0:
            self.product *= num
            self.pre_mul.append(self.product)
        else:
            self.product = 1
            self.pre_mul = []

    def getProduct(self, k: int) -> int:
        if k == len(self.pre_mul):
            return self.pre_mul[-1]
        elif k > len(self.pre_mul):
            return 0
        else:
            return int(self.pre_mul[-1]/self.pre_mul[-1-k])