713) Subarray Product Less Than K

25 May 2021 in Algorithms

• 이렇게 하면 time limit 뜬다! 그래서 sliding window로 처리해줘야함. 문제 키워드에서도 contiguous가 나오는데, 이거 나오면 슬라이딩 윈도우 생각하기를.
• https://www.youtube.com/watch?v=NcD0CZLd6xM 이 영상에서 연속된 subarray 어케 세는지 배웠다.

연속된 subarray 세는 법!

• 새로 추가된 끝원소가 포함된 subarray의 개수를 기존 subarray 개수에 더해준다고 생각하면 편하다.

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int prd = 1;
        int left=0;
        int cnt=0;
        //right 를 기준으로, subarray를 세줄 것이다.
        int right=0;
        while(right < nums.length){
            prd*=nums[right];
            if(prd<k){
                cnt += right-left+1;
                right++;
            }else{
                while(prd>=k && left<=right){
                    prd/=nums[left];
                    left++;
                }
                if(left==right){
                    //나눠줘야함
                    prd/=nums[right];
                    while(left<nums.length && nums[left]>=k){
                        left++;
                    }
                    right=left;
                }else{
                    cnt+=right-left+1;
                    right++;
                }
            }
        }
        return cnt;
    }
}

• 하….. ㅈㄴ 많이 틀렸다… 후…
• 계속 안풀려서 결국엔 그림 그렸다. 그림 그리니까 좀 더 생각이 명확해 지는 것 같다. 그림을 그려라.. 좋은 그림은 아닌데, 어쨌든 지저분한 방식으로 풀면 더 그림이 도움된다..

다른 풀이

• 아주 깔끔한 다른 풀이… ^^,,
• 일단 for문으로 처리하면, 범위 생각을 좀 덜 할 수 있는 듯 싶다.

1. right를 곱해준다.
2. 만약에 곱한 값이 k보다 커지면, left를 나눠준다. 계속. 그리고, left 범위를 신경을 안 써줬는데 , 왜냐믄,, prod가 k 보다 큰 동안이니까 이게

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0; // nums = [1], k = 1
        int count = 0;
        int left = 0;
        int prod = 1;
        for (int i = 0; i < nums.length; i++) {
            prod *= nums[i];
            while (prod >= k) {
                prod /= nums[left++];
            }
            count += i - left + 1;
        }
        return count;
    }
}

• 또 다른 풀이

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int p=1;
        int i=0;
        int j=0;
        int ans=0;
        while(i<nums.length)
        {
            if(nums[i]>=k){p=1;i++;j=i;continue;}
            p*=nums[i];
            while(j<=i && p>=k)
            {
                p/=nums[j];
                j++;
            }
            ans+=(i-j+1);
            i++;
        }
        return ans;
    }
}