1352. Product of the Last K Numbers

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

 

입력으로 들어오는 숫자가 들어온다.

getProuct() 는 배열의 뒷 부분부터의 요소의 곱을 출력 한다.

 

	cmd	원소	출력
1	add(1)	[1]
2	add(2)	[1, 2]
3	add(3)	[1, 2, 3]
4	add(0)	[1, 2, 3, 0]
5	add(8)	[1, 2, 3, 0, 8]
6	add(2)	[1, 2, 3, 0, 8, 2]
7	getProduct(1)	[1, 2, 3, 0, 8, 2]	2
8	getProduct(2)	[1, 2, 3, 0, 8, 2]	16
9	add(8)	[1, 2, 3, 0, 8, 2, 8]
10	getProduct(1)	[1, 2, 3, 0, 8, 2, 8]	8
11	getProduct(4)	[1, 2, 3, 0, 8, 2, 8]	0
12	getProduct(3)	[1, 2, 3, 0, 8, 2, 8]	32

 

Source

최초 코드는 time limit 으로 실패 

getProduct() 의 출력값은 마지막요소 부터 k 까지 모든 곱을 출력을 하면 된다.

num 의 입력범위는 -100 에서 100 사이, k 의 횟수는 40000 까지 

 

class ProductOfNumbers {
public:
    ProductOfNumbers() {
        cin.tie(0);
        std::ios::sync_with_stdio(false);
    }

    void add(int num) {
        ll.push_front(num);
    }

    int getProduct(int k) {
        
        int sol = 1;
        list<int>::iterator it = ll.begin();
        while (k) {
            sol *= *it;
            if (sol == 0) {
                return 0;
            }
            k--;
            it++;
        }
        return sol;
    }
    list<int> ll;
};

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

 

 

배열의 요소가 0 입력되면 해당 배열 위치부터 다시 제 계산 해야 한다.

DP 로 접근 하려다가 잘못 풀어서 다시 확인..

class ProductOfNumbers {
public:
    ProductOfNumbers() {
    }

    void add(int num) {
        if (num)
            arr.push_back(arr[arr.size() - 1] * num);
        else
            arr = {1};
    }

    int getProduct(int k) {
        return k < arr.size() ? arr[arr.size() - 1] / arr[arr.size() - k - 1]  : 0;
    }
    vector<int> arr = {1};
};

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