1352. Product of the Last K Numbers

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

Product of the Last K Numbers - LeetCode

 

1. 문제와 예제, 그리고 제약사항

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.

 

 

2. 문제 풀이

 

문제를 해석하면 다음과 같다. 3개의 메소드가 주어진다.

먼저 ProductOfNumber() 메소드는 Stream을 초기화하는 메소드다. 

다음은  add(int num) 메소드다. 이 메소드는 주어진 num을 stream에 추가하는 역할이다.

마지막으로 getProduct(int K) 메소드다. 이 메소드는 stream에 존재하는 데이터를 상수 k만큼 뒤에서 꺼내서 그 상수를 더한 값을 return 하는 메소드다.

예를 들어 stream(list)에 1, 2, 3, 4 가 들어있는 경우 상수 k로 3이 주어지면 2 * 3 * 4, 24를 return하면 된다.

 

단순한  문제로 보여지지만 getProduct 메소드에서 반복문을 통해 데이터를 가져와 연산 후 return하게 되면 Time Limit Exceeded가 발생하게 된다.

 

이 문제는 add메소드 호출시 각각 주어진 num 값을 저장하지 않고 연산까지 한 후 저장하는것이 포인트다.

아래 풀이 소스 코드와 주석을 통해 풀이를 같이 적어두었다.

class ProductOfNumbers {
    // stream data를 저장할 list 선언
    List<Integer> arr;
    // 현재 list에 담겨진 값을 저장하기 위한 변수
    int prd;
    
    public ProductOfNumbers() {
    	//list 및 변수 초기화
        arr = new ArrayList<>();
        prd = 1;
    }
    
    public void add(int num) {
    	// 중요한 부분이다.
        // list에 add 메소드를 통해 값을 넣다가
        // 0을 만나게되면 list를 초기화 해준다.
        // 왜냐하면 list에는 연산된 값을 집어넣도록 하였는데
        // 지금까지 연산된 값을 들고 있는 prd에 0을 곱하게 되면 0이기 때문이다.
        // 그렇기 때문에 0 이전까지 저장했던 list값이 의미가 없어지게 된다.
        // 그러므로 list를 초기화 하고 연산 값을 저장하는데 사용한 변수도 1로 초기화 한다.
        if(num ==0){
            arr = new ArrayList<>();
            prd = 1;
        }else{
        	// 연산 값을 저장하는 변수에 현재 입력된 num을 곱하여 저장한다.
            prd *= num;
            // 연산된 결과를 리스트에 저장한다.
            arr.add(prd);
        }
    }
    
    public int getProduct(int k) {
        // 위에서 0을 만나면 list를 초기화하고
        // 아닌경우에만 연산된 결과를 저장하였다.
        // list의 사이즈가 k보다 작다는 말은
        // add메소드를 호출시 0이 한번 이상은 호출되었다는 말과 같다.
        // 예를 들어 1, 0 , 3, 4가 add 함수를 호출하였다고 가정해보자.
        // k가 4가 주어졌을 때 1 * 0 * 3 * 4 = 0으로써
        // 중간에 0을 만나기 때문에 결과 값은 0을 리턴하게 된다.
        if(arr.size() <k return 0;
        
        // 리스트에 저장된 연산 값을 불러온다.
        int res = arr.get(arr.size() -1);
        
        // arr.size()가 k와 같다는 말은
        // 단 한번도 add 메소드에 0을 받은적이 없다는 말이다.
        // 그렇기 때문에 위에 res값을 반환한다.
        if( arr.size() == k){
            return res;
            
        // arr.size()가 k와 같지 않다는 말은
        // 전체 값을 호출하는 것이 아닌 뒤에서 부터 상수 k까지의 누적값이 필요하다.
        // 그렇기에 전체 누적 값이 담겨있는 res에서 
        // list에 있는 값 중 k 이전까지의 누적 값을 나누게 되면 k까지의 누적곱셈값이 되게 된다.
        
        // 예를 들어 2 3 4 5이 주어졌다면 res값은 전체 곱인 120이 된다.
        // k가 2라고 하면 우리가 원하는 값은 4 * 5 = 20이다.
        // list에는 각각의 누적 합이 담겨 있고 전체 res값에서 k전까지의 누적합을 담고 있는
        // 인덱스의 list 값을 찾아 나눠주면 k만큼의 누적 합이 나오게 된다.
        }else{
            return res/arr.get(arr.size()-1-k);
        }
    }
}