[C] LeetCode 713. Subarray Product Less Than K

문제

번역

nums 라는 정수 배열과 정수 k가 주어졌을때, 부분배열의 모든 원소의 곱이 k보다 작은 부분배열의 개수를 반환해라.

접근 방법 및 소스 코드

투 포인터를 사용하면 된다.

i를 0부터 numsSize-1까지 반복하면서 i에 해당하는 인덱스를 곱셈의 시작점으로 쓴다.

포인터 j를 한칸씩 뒤로 가면서 곱해본다. 이때, 곱한 값이 k보다 작은지 매번 검사하면서 곱한다.

그래서 가능한 가장 큰 j를 구한 뒤, counter에 해당 부분배열 길이 만큼 다시 더해준다.

그 다음 i를 한칸 밀고, 기존에 곱했던 값에서 배열의 i번째의 값만큼 다시 나눠준다.

그리고 j를 또 한칸씩 뒤로 가면서 곱해본다... 이를 끝까지 반복한다.

 

int numSubarrayProductLessThanK(int* nums, int numsSize, int k) {
    int j=0,prod=1,ans=0;
    for(int i = 0 ; i < numsSize ; i++) {
        if(j < i) {
            j = i;
            prod = 1;
        }
        while(j < numsSize && prod * nums[j] < k) prod *= nums[j++];
        if(i < j) {
            ans += j - i;
            prod /= nums[i]; 
        }
    }  
    return ans;
}

 

왜인지는 모르겠지만 문제해결 수업이 있는 날 내 블로그 방문자가 생각보다 높다..