Leetcode713.SubarrayProductLessThanK

소스코드

문제

• 713. SubarrayProductLessThanK

풀이 (brute-force)

• 시간복잡도 O(n 제곱)
• 아래 문제 풀 때, 실수는 end 를 원위치 시키는 것
• 연속적이고 부분배열을 구하는거면 Window 를 고려

   /**
     * 10  count 1
     * 10 * 5 -> count 2
     * 10 * 5 * 2 < 100 -> 멈춤
     * 5 ->    count 3
     * 5 * 2 -> count 4
     * 5 * 2 * 6 -> count 5
     * 2 -> count 6
     * 2 * 6 -> 7
     * 6 -> 8
     *
     * brute-force
     * 시간복잡도 O(n 제곱)
     */
    fun numSubarrayProductLessThanKBruteForce(nums: IntArray, k: Int): Int {
        var left = 0
        var right = 0
        var count = 0
        var tmp = 1
        val size = nums.size

        // 이건 윈도우 개념이 아님. 잘못 풀었음. right 와 start 를 움직이면서 부분집합의 개수를 구함
        while (left < size) {
            tmp *= nums[right]
            if (tmp < k && right < size) {
                count++
                right++
            } else {
                left++
                right = left
                tmp = 1
            }

            if (right == size) {
                left++
                right = left
                tmp = 1
            }
        }
        return count
    }

풀이 (Window)

• window 크기는 부분배열의 크기
• right 를 움직이면서 window 부분배열의 곱이 k 이면 left 를 이동시킴

    fun numSubarrayProductLessThanKUsingWindow(nums: IntArray, k: Int): Int {
        // edge case
        if (k <= 1) {
            return 0
        }

        var count = 0
        var product = 1

        var left = 0
        var right = 0

        // right 를 이동시키면서 window 를 늘려나가고, k 를 넘어서면 left 를 이동시킨다.
        while (right < nums.size) {
            product *= nums[right]

            // product 이 k 보다 크다면 left 를 증가시키면서 window 를 이동
            while (product >= k) {
                product /= nums[left++]
            }

            // right - left + 1 은 부분집합의 개수다. (= window size )
            count += right - left + 1
            right++
        }
        return count
    }