[LeetCode] 713. Subarray Product Less Than K

https://leetcode.com/problems/subarray-product-less-than-k/description/

Leetcode - Subarray Product Less Than K

문제 유형 : 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

 

정수 배열 nums와 정수 k가 주어진다. 전체 곱이 k보다 작은 부분배열들의 개수를 구하시오.

 

풀이

슬라이딩 윈도우를 이용하여 풀어주면 된다.

단순히 모든 부분배열을 만들어도 풀 수도 있다.

 

왼쪽 포인터와 오른쪽 포인터를 만든다.

오른쪽 포인터로는 한 칸씩 확장하면서, 부분곱에 곱한다.

만약 부분곱이 k보다 커지면, 왼쪽 포인터를 오른쪽으로 당기면서 부분곱에 나눈다.

부분곱이 k보다 작아질 때까지 반복한다.

슬라이딩 윈도우의 크기만큼 계속 누적시킨다.

최종적으로는 답이 구해져있다.

 

코드

C++

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        const int n = nums.size();
        
        int cnt = 0;
        int product = 1;
        for (int i = 0, j = 0; j < n; j++) {
            product *= nums[j];
            while (i <= j && product >= k) {
                product /= nums[i++];
            }
            cnt += j - i + 1;
        }
        return cnt;
    }
};