Subarray Product Less Than K

Subarray Product Less Than K

Subarray Product Less Than K - LeetCode

문제 내용 : 주어진 nums의 집합 내 연속되는 부분 집합의 곱이 주어진 k 보다 작은 경우의 수는?

접근 방법

1. Permutation

처음에는 permutation으로 접근 하려고 했는데, 다음 2가지를 보고 포기 했다.

• 0 < nums.length <= 50000
• (contiguous) subarrays

50000개의 subarray를 모두 검사하는 것은 문제 목표에 부합하지 않은 것으로 보이고, 연속된 부분 집한을 대상으로 하기때문에 순서가 없는 모든 조합을 검사 하는것도 맞지 않다.

 

2. sliding window

다음과 같은 array가 주어졌다고 했을 때

[1,2]

3이 목표 값이라고 하면 [1],[2],[1,2] 3가지 경우가 된다.

[1,2,3] 이 주어진 Array이고 3이 목표 값이라고 하면

[1][2][1,2][3] 이 답이 된다.

만약 목표 값이 7이라고 하면

[1][2][3][1,2][2,3][1,2,3] 으로

6가지가 답이 된다. 

상기와 같은 순서를 보면 다음과 같이 계산 할 수 있다.

• 0번째 index의 곱셈 누적이 목표 값보다 적다면 = 1가지 경우
• 1번째 index가 곱셈 누적이 목표 값보다 적다면 = 2가지 경우 (0번째를 더한 총은 3가지 경우)
• 2번째 index가 곱셈 누적이 목표 값보다 적다면 = 3가지 경우 (0,1번째 인덱스를 더한 경우는 6가지 경우) 

즉 현재의 index까지 곱셈해서 누적한 값이 목표값 k보다 적다면 해당 인덱스를 추가하면

• 현재의 index + 1 가지

가 답이 된다고 할 수 있다. 그렇다면 곱셈 누적이 목표 값보다 높다면 어떻게 해야할까?

[1,2,3] 이 주어진 Array이고 3이 목표 값이라고 하면 [1][2][1,2][3] 이 답이 된다고 했다.

이를 풀어 보겠다.

곱셈 누적은 다음과 같다.

[1,2,6]

• 0번째 index = 1가지 경우
• 1번째 index = 2가지 경우
• 2번째 index는 곱셈 누적이 3보다 높음
  • 1*2*3 => 목표값보다 높음
  • 2*3 => 목표값보다 높음
  • 3 => 목표값 보다 낮음

즉 index 2인 경우는 나올수 있는 값의 수는 2 + 1 3가지 겠지만 여기서 2가지 경우의 수를 빼줘야 한다.

6이라는 누적값에서 가장 좌측 0 index 1 값을 나누어 보았을 때 목표값보다 높으면

다시 좌측 index를 1로 만들어서 나누어 본다. 6/2 = 3이 된다. 2*3의 경우는 경우의 수에서 빼야 하니까

곱셈 누적은 3으로 만들고 나누어지는 index는 1을 더해준다.

• 현재의 index 2 - 좌측 index 2 + 1 = 1가지 경우의 수

만 남게 된다.

이를 코드로 만들면 다음과 같다.

var numSubarrayProductLessThanK = function(nums, k) {
    let product = 1;
    let left = 0;
    let count = 0;
    
    for(let right = 0; right < nums.length; right++){
        product *= nums[right];
        
        while(k <= product && left <= right){
            product /= nums[left++];
        }
        
        count += right - left + 1;    
    }
    
    return count;
    
};

O(N) 시간 복잡도를 갖는다.

본 문제에서 배워야 할 것은 

단조함수 형태의 그래프가 Prefixsum 될 수 있다면 sliding window의 가능성이 생긴다는 것이다.