[LeetCode] 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold - LeetCode

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

 

 

주어진 배열에서 길이가 k인 sub배열을 추출했을때, 그 평균이 threshold 이상인 개수를 구하는 문제이다.

매우 쉬운 문제인듯한데 이 문제 난이도가 Medium이라 계속해서 뭔가 있나 보았다.

하지만 없었다.

 

풀이는 아래와 같다

먼저 평균값을 구하기는 귀찮으니 threshold를 애초에 threshold * k로 총합으로 바꿔주자.

그 뒤 0~k-1 까지의 sub배열의 합 sum을 구해준다.

이 합이 threshold 이상인지 체크해 이상이면 ret++을 해준다.

그 후, i=1 to 배열사이즈-k 까지 훑어주며

sum에서 i-1을 뺴주고, i+k-1을 더해준다.

이러면 한칸씩 움직인 sub배열의 합이 된다.

이를 threshold와 비교하고 ret++을 해주는 작업을 반복한다.

 

전체 풀이 코드

 

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        threshold *= k;
        int sum = 0;
        for (int i=0; i<k; i++) sum+=arr[i];
        int ret = sum>=threshold;
        for (int i=1; i<=arr.size()-k; i++) {
            sum += -arr[i-1]+arr[i+k-1];
            ret += sum>=threshold;
        }
        return ret;
    }
};