[LeetCode] 713. Subarray Product Less Than K

713. 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.

 

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

 

Constraints:

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

---

문제 풀이

• k 값보다 작은 부분 배열의 갯수를 구하자.
• 제한 사항은 3 * 10 ^ 4 이다. 
• 브루트 폴스로 부분 배열을 모두 검색하려면 O(N^2) 시간이 걸리며 아슬아슬 하게 통과 될 수도 있다. 
• 부분 배열 문제는 보통 슬라이딩 윈도우나 해쉬 테이블을 사용한다. 
• 포인터를 두개 사용하는데 끝 포인터를 계속 옮겨주면서, 맨 처음 인덱스부터 시작 포인터를 늘려준다.
• 시작 포인터 값으로 끝 포인터까지 곱해준 값을 계속해서 나눠보고 그 값이 k 보다 작아지면 끝낸다. 
• 이때 마지막 포인터 - 시작 포인터 + 1 를 계산한 값이 현재 시작 포인터 부터 마지막 포인터 안에 들어있는 부분 배열을 의미한다. 
• 왜냐하면 마지막 포인터가 하나 증가함에 따라 곱해야하는 변수가 하나 추가되기 때문이다. 
  • 예를 들어, 10, 5, 2, 6 배열에서 5, 2, 6 이 k = 100 을 넘지 않을때,
  • 시작 포인터는 5, 끝 포인터는 6 이라고하자, 이때 기존재, 10, 5, 2 는 이미 카운터가 되어있다.
  • 그 후 끝 포인터가 하나 증가해서 6 이되고 시작 포인터는 부분 배열에 포함시킬 수 없어서 1 개를 증가시킨다. 
  • 그렇다면, 5, 2, 6 에서 끝 포인터 3 (6) - 시작 포인터 1 (5) + 1 가 의미하는 배열들은
  • [5, 2, 6], [2, 6], [6] 이렇게 세개가 된다. 
• 정답으로 요구하는 것이 연속된 부분 배열이고, 포인터가 선택 되었을때 총 곱이 이미 k 보다 적기 때문에 
• 새로 생긴 변수부터 시작 포인터까지의 모든 부분 배열을 이렇게 계산할 수 있다. 

소스 코드

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans = 0
        total, p1 = 1, 0
        if k <= 1:
            return ans
        
        for i in range(len(nums)):
            total *= nums[i]
            while total >= k:
                total //= nums[p1]
                p1 += 1
            ans += i - p1 + 1
        return ans