Leetcode 1352. Product of the Last K Numbers

문제

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.

Implement the ProductOfNumbers class:

ProductOfNumbers() Initializes the object with an empty stream.
void add(int num) Appends the integer num to the stream.
int getProduct(int k) Returns the product of the last k numbers in the current list. You can assume that always the current list has at least k numbers.
The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

문제 설명

정수 스트림을 받아들이고, 마지막 k개의 정수의 곱을 반환하는 알고리즘을 설계하시오.

클래스 정의

• ProductOfNumbers 클래스:
  • ProductOfNumbers(): 빈 스트림으로 객체를 초기화한다.
  • void add(int num): 정수 num을 스트림에 추가한다.
  • int getProduct(int k): 현재 리스트에서 마지막 k개의 숫자의 곱을 반환한다.

제한 사항

• 언제든지 k개의 숫자의 곱이 32비트 정수형 범위 내에서 표현 가능함이 보장된다.
• 입력되는 k는 항상 현재 리스트에 있는 숫자 개수 이하로 주어진다.

---

예시

입력:

["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

출력:

[null,null,null,null,null,null,20,40,0,null,32]

설명:

ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20. 마지막 2개의 숫자의 곱: 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. 마지막 3개의 숫자의 곱: 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. 마지막 4개의 숫자의 곱: 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. 마지막 2개의 숫자의 곱: 4 * 8 = 32

---

제한

• $0 <= num <= 100$
• $1 <= k <= 4 * 10^4$
• 최소 $10^4$ 번 호출이 일어난다.
• 숫자의 곱은 절대 32비트 signed 값을 넘지 않는다.

---

풀이

• 0이 등장할때를 제외하면 일반적인 누적곱이다.
• 0이 등장한다면, 0을 기준으로 모든 0을 포함한 모든 왼쪽의 값들을 곱에 포함할때 0이 된다.
• 즉, 누적합을 초기화 하고, 누적합의 길이보다 큰 요청이 오면 무조건 0을 반환하게 한다.

class ProductOfNumbers:

    def __init__(self):
        self.acc = 1
        self.prod = []

    def add(self, num: int) -> None:
        if num != 0:
            self.acc *= num
            self.prod.append(self.acc)
        else:
            self.acc = 1
            self.prod = []

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


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