ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1352. Product of the Last K Numbers
    릿코드(LEETCODE) 2020. 2. 16. 15:55
    반응형

    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);
     */

     

     

    반응형

    '릿코드(LEETCODE)' 카테고리의 다른 글

    1310. XOR Queries of a Subarray  (0) 2020.02.16
    1309. Decrypt String from Alphabet to Integer Mapping  (0) 2020.02.16
    1143. Longest Common Subsequence  (0) 2020.02.15
    119. Pascal's Triangle II  (0) 2020.02.14
    118. Pascal's Triangle  (0) 2020.02.14

    댓글

Designed by Tistory.