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]
→ getProduct(2): 5 × 4 = 20
→ getProduct(3): 2 × 5 × 4 = 40
→ getProduct(4): 0 × 2 × 5 × 4 = 0
→ add(8) 후 목록: [3, 0, 2, 5, 4, 8]
→ getProduct(2): 4 × 8 = 32

해결 전략: 누적 곱(접두사 곱) 활용

getProduct가 호출될 때마다 마지막 k개 숫자를 일일이 곱하면 O(k)의 시간이 걸립니다. 하지만 누적 곱(prefix product) 배열을 활용하면 각 연산을 O(1)에 처리할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

초기화: 배열을 생성하고 기준점 역할을 하는 값 1을 미리 넣어둡니다.
add(num): num이 0이라면 배열을 모두 비우고 다시 1을 삽입합니다. 0이 포함되는 순간 이후의 곱은 항상 0이 되므로, 0을 경계로 구간을 새로 시작하는 것입니다. num이 0이 아니라면 마지막 원소에 num을 곱한 값을 추가합니다.
getProduct(k): 배열의 크기를 n이라 할 때, k > n − 1이면 요청한 범위가 마지막 0 지점을 넘어선다는 의미이므로 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);   // 나눗셈 기준점으로 1 삽입
    }

    void add(int num) {
        if (num == 0) {
            dq.clear();          // 0 이후의 곱은 모두 0이므로 초기화
            dq.push_back(1);
        } else {
            dq.push_back(dq.back() * num);   // 누적 곱 저장
        }
    }

    int getProduct(int k) {
        int n = (int)dq.size();
        // 범위가 0 지점을 넘으면 곱은 0
        return k > n - 1 ? 0 : dq[n - 1] / dq[n - k - 1];
    }
};

int 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)

출력

복잡도 분석

시간 복잡도: add와 getProduct 모두 O(1)입니다.
공간 복잡도: 저장된 숫자의 개수에 비례하여 O(n)입니다.

누적 곱과 0 처리 규칙만 정확히 이해하면, 반복적인 곱셈 없이도 마지막 k개 숫자의 곱을 매우 효율적으로 조회할 수 있습니다.