[LeetCode/Kotlin]Medium - 1343. 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

문제

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Constraints:

• 1 <= arr.length <= 105
• 1 <= arr[i] <= 104
• 1 <= k <= arr.length
• 0 <= threshold <= 104

풀이

나의 풀이법

풀이 접근 과정

처음엔 무작위로 뽑아서 부분집합을 만드는 줄 알고 시간초과 없이 어떻게 할까 생각하다가 프로그래머스면 몰라도 릿코드는 그런 짓을 하지 않을 것이라 생각하고 문제를 다시 읽었다.

역시나 그냥 순서대로 이웃된 부분 집합을 따지는 문제였다.

슬라이딩 윈도우 느낌? 그런데 난 그 알고리즘을 모르므로 그냥 풀었다 !

최종 소스코드

class Solution {
    fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
        var sum = 0
        var answer = 0
        
        arr.forEachIndexed { idx, i ->
            sum += i
            if (idx >= k) sum -= arr[idx-k]
            if (idx >= k-1 && sum/k >= threshold) answer++
        }

        return answer
    }
}

1. arr에서 차근차근 k 개수가 될 때까지의 값을 sum에 더한다.
2. 만약 인덱스가 k보다 크거나 같으면 제일 처음 더한 값을 빼주고 새로운 값을 더해준다.
3. 만약 idx가 k-1과 같거나 크고 합의 평균이 임계값보다 같거나 크면 answer에 개수를 더한다.

• 시간복잡도: O(N)
• 공간복잡도: O(1)

---

 

Comment

그렇게 까다로운 문제가 아니었다. 문제를 푸는데 소요되는 시간은 정말 짧았다.

오랜만에 간단한 문제를 푸니 기분이 좋당 ><