[leetcode] Subarray Product Less Than K

문제

• 링크
• 배열 nums와 정수 k가 주어진다. 모든 값의 곱이 k보다 작은 subarray 개수를 구해야한다.
• 제약 조건
  • 배열 길이: 1 <= nums.length <= 3 * 10^4
  • 배열 값 범위: 1 <= nums[i] <= 1000
  • k 범위: 0 <= k <= 10^6

풀이

풀기 전

• 처음에는 브루트포스로 모든 경우의 수를 계산해보려고 했다. 그러면 배열 길이를 n이라고 했을 때, subarray 개수는 총 n(n+1)/2개가 된다. n의 최대값이 30,000이므로, 약 4억 5천개..는 겨우 통과할 수도 있을 거 같은 값이라 애매했다.
• 사실 모든 subarray를 확인하는 건 최악의 경우이고, 만약 특정 subarray가 조건을 만족한다면 해당 subarray의 subarray도 조건을 만족한다는 걸 알 수 있다. 그래서 특정 인덱스에서 조건을 만족하는 가장 큰 subarray를 찾으면 된다. 처음에는 재귀로 풀려고 했는데 복잡해졌다. 그래서 discussion 참고해서 슬라이딩 윈도우 방식으로 풀었다.

코드

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;

		// left는 탐색하는 subarray의 가장 왼쪽 인덱스가 된다.
		// right는 탐색하는 subarray의 가장 오른쪽 인덱스가 된다.
        int left = 0, right = 0;
        int val = 1;  // 매번 subarray 값의 곱을 계산하지 않기 위해 공통으로 사용할 값이다.
        while (right < n) {
            val *= nums[right];  // subarray의 가장 오른쪽 값을 곱해준다.

			// 조건을 만족하지 않는 동안 subarray의 길이를 줄여준다.
            // 처음부터 조건을 만족하면 left의 변화는 없다.
            while (val >= k) {
            	// left가 right랑 같으면 subarray 길이가 1이므로 중단한다.
                if (left == right)
                    break;
                    
                // subarray에서 제외할 값을 val에서 나눠준다.
                val /= nums[left];
                left++;
            }

			// 조건을 만족하면 추가된 subarray 개수를 더해준다.
            // 원래 subarray에 속하는 총 subarray 개수는 subarray.length(subarray.length+1)/2 이지만, 중복된 subarray가 있기 때문에 right-left+1만 더해준다.
            // 예를 들어 조건을 만족한 subarray=[2, 3, 1]일 때, right가 이동한 뒤 1이 추가돼서 조건을 만족한 것이기 때문에 1이 속한 subarray 개수만 추가로 더해주면 된다.
            // 여기선 [1], [3, 1], [2, 3, 1]이 해당한다.
            if (val < k)
                ans += right - left + 1;

			// 다음 인덱스로 이동한다.
            right++;
        }

        return ans;
    }
}

• 예시 nums = [10,5,2,6], k = 100
  1. left = 0, right = 0
     val = 1 * nums[right] = 1 * 10 = 10
     val < k 이므로 left 유지
     ans += right - left + 1 => +1
     right 이동
  2. left = 0, right = 1
     val = 10 * nums[right] = 10 * 5 = 50
     val < k이므로 left 유지
     ans += 1 - 0 + 1 => +2
     right 이동
  3. left = 0, right 2
     val = 50 * nums[right] = 50 * 2 = 100
     val >= k이므로 val /= nums[left] 해주면 100 / 10 = 10이고, left는 1 증가
     ans += 2 - 1 + 1 => +2
     right 이동
  4. left = 1, right = 3
     val = 10 * nums[right] = 10 * 6 = 60
     val < k이므로 left 유지
     ans += 3 - 1 + 1 => +3
     right 이동
  5. right가 배열 범위를 벗어나서 루프 종료

푼 후

• 앞에서 조건이 확인된 subarray는 뒤에서 다시 확인하지 않는다라는 아이디어가 중요한 거 같다. 그래서 새로 추가된 값에 대해서만 다시 subarray 조건을 체크할 수 있다.