[LeetCode] 1352. Product of the Last K Numbers

https://leetcode.com/problems/product-of-the-last-k-numbers/description/

Product of the Last K Numbers

문제 유형: 부분합, 슬라이딩 윈도우

문제 난이도: Medium

 

문제

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개의 숫자들을 곱한 값을 리턴합니다.

 

풀이

부분곱 / 부분곱을 이용해서 빠른 시간에 구할 수 있도록 해보자.

처음에, 배열에 1을 넣는다. 나눗셈을 편하게 하기 위해서이다.

 

add를 다음과같이 구현할 수 있다:

data에 매번 곱들을 누적한 값들을 맨 뒤에 추가한다. 이전 마지막이 0이면 그냥 처음부터 넣는다.

만약 이번에 추가하는 숫자가 0이라면, zeros배열에 인덱스를 저장한다.

 

getProduct를 다음과 같이 구현할 수 있다:

만약 n-1-k가 음수라면, data[n-1]을 리턴한다.

zeros배열에서 n-1-k보다 큰 정수가 있다면, 중간에 0이 있다는 뜻으로, 0을 리턴한다.

만약 data[n-k]가 음수라면, data[n-1]을 리턴한다.

모두 아니라면, data[n-1] / data[n-1-k]를 리턴한다.

 

더 최적화가 가능하다:

zeros배열 대신, 마지막으로 0이 등장한 곳을 추적하기 위해 마지막 0 이후로의 카운트인 size 정수를 만든다.

add를 하면서, 0이면 누적곱 대신 1을넣고, size를 0으로 초기화한다. 새로 초기화가 된다고 생각하면 된다.

getProduct에서는 k가 size보다 크면 0을 반환한다. 0을 반드시 포함하게 되기 때문이다.

아니라면, data[n-1]/data[n-1-l]를 반환한다.

 

코드

C++(이진탐색 이용)

class ProductOfNumbers {
private:
    vector<int> data;
    vector<int> zeros;
public:
    ProductOfNumbers() {
        data = {1};
    }
    
    void add(int num) {
        if(data[data.size()-1] != 0) {
            data.emplace_back(num * data[data.size()-1]);
        } else {
            data.emplace_back(num);
        }
        if(num == 0) {
            zeros.emplace_back(data.size()-1);
        }
    }
    
    int getProduct(int k) {
        int n = data.size();
        int divIdx = n-k-1;
        if(divIdx < 0) {
            return data[n-1];
        } else if(upper_bound(zeros.begin(), zeros.end(), divIdx) != zeros.end()) {
            return 0;
        } else if(data[divIdx] == 0) {
            return data[n-1];
        }
        return data[n-1]/data[divIdx];
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

 

Go(더 최적화된 풀이)

type ProductOfNumbers struct {
    data []int
    size int
}


func Constructor() ProductOfNumbers {
    return ProductOfNumbers{data: []int{1}, size: 0}
}


func (this *ProductOfNumbers) Add(num int)  {
    if num != 0 {
        this.data = append(this.data, this.data[len(this.data)-1] * num)
        this.size++
    } else {
        this.data = append(this.data, 1)
        this.size = 0
    }
}


func (this *ProductOfNumbers) GetProduct(k int) int {
    if k > this.size {
        return 0
    }
    return this.data[len(this.data)-1] / this.data[len(this.data)-1-k]
}


/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(num);
 * param_2 := obj.GetProduct(k);
 */