C++의 마지막 K 숫자의 곱

두 가지 방법을 지원하는 ProductOfNumbers라는 클래스를 구현했다고 가정해 보겠습니다.

add(int num):현재 숫자 목록 뒤에 숫자 num을 추가합니다.
getProduct(int k):현재 목록에서 마지막 k개의 숫자를 곱한 값을 반환합니다.

항상 현재 목록에 최소한 k개의 숫자가 있다고 가정할 수 있습니다. 예를 들어, 입력이 다음과 같은 경우 - add(3), add(0), add(2), add(5), add(4), getProduct(2), getProduct(3), getProduct(4), add(8), getProduct(2), 출력은 (각 함수 호출 후) -

[3], [3, 0], [3, 0, 2], [3, 0, 2, 5], [3, 0, 2, 5, 4], then (5 * 4) = 20, then (2 * 5 * 4) = 40, then (0 * 2 * 5 * 4) = 0, then [3, 0, 2, 5, 4, 8], then (4 * 8) = 32.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

초기화 섹션에서 배열을 만들고 1을 넣습니다.
add() 메소드는 num을 취합니다
num이 0이면 배열을 지우고 1을 삽입하고, 그렇지 않으면 last_element * num을 배열에 삽입
getProduct() 메서드는 k를 입력으로 사용합니다.
n :=배열의 크기
k> n – 1이면 0을 반환하고 그렇지 않으면 dp[n – 1] / dp[n – k – 1]

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class ProductOfNumbers {
public:
   vector <int> dq;
   ProductOfNumbers() {
      dq.push_back(1);
   }
   void add(int num) {
      if(num == 0){
         dq.clear();
         dq.push_back(1);
      }
      else{
         dq.push_back(dq.back() * num);
      }
   }
   int getProduct(int k) {
      int n = (int)dq.size();
      return k > n - 1? 0 : dq[n - 1] / dq[n - k - 1];
   }
};
main(){
   ProductOfNumbers ob;
   (ob.add(3));
   (ob.add(0));
   (ob.add(2));
   (ob.add(5));
   (ob.add(4));
   cout << (ob.getProduct(2)) << endl;
   cout << (ob.getProduct(3)) << endl;
   cout << (ob.getProduct(4)) << endl;
   (ob.add(8));
   cout << (ob.getProduct(2)) << endl;
}

입력

add(3)
add(0)
add(2)
add(5)
add(4)
getProduct(2)
getProduct(3)
getProduct(4)
add(8)
getProduct(2)

출력