Daily LeetCode Challenge - 974. Subarray Sums Divisible by K

Problem From.

https://leetcode.com/problems/subarray-sums-divisible-by-k/

오늘 문제는 주어진 array 의 subarray 중에서 그 합이 k 로 나누어떨어지는 subarray 의 수를 구하는 문제였다.

각 subarray 의 합은 prefix sum 알고리즘으로 구하면 되었다.
처음에는 prefix sum 알고리즘으로 구한 각 array 의 합을 k 로 나누어서 나머지가 0 인 경우를 구했는데 실행시간이 O(N^2) 으로 통과하지 못했다.

위에서 한 풀이를 응용하여, prefix sum 알고리즘으로 구한 sum 배열이 있다고 생각했을때,
(sum[j] - sum[i]) % k == 0 인 경우에 답을 1씩 올려줬어야 했는데, 이 경우는 바꿔서 생각하면
sum[j] % k == sum[i] % k 인 경우를 보면 되었다.
그래서 주어진 array 를 처음부터 더해 나가면서 각 합을 % k 했을때 같은 경우의 수가 몇번 있는지를 체크해서 더해주면 되는 문제였다.

class Solution {
    fun subarraysDivByK(nums: IntArray, k: Int): Int {
        
        var answer = 0
        var sum = 0
        val map = hashMapOf<Int, Int>()
        map[0] = 1
        
        nums.forEach { num ->
            sum += num
            val remainder = (sum % k + k) % k
            answer += map.getOrDefault(remainder, 0)
            map[remainder] = map.getOrDefault(remainder, 0) + 1
            
        }
        
        return answer
    }
}

위 문제의 시간복잡도는 O(N) 이 된다.