PrefixSum_Leetcode_974 Subarray Sums Divisible by K [swift]

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

 

이론

배열의 부분합을 구할 때,

✅ prefixSum[i]는 인덱스 0부터 i까지의 합을 의미합니다.

✅ prefixSum[j]는 인덱스 0부터 j까지의 합을 의미합니다.

 

어떤 i와 j가 있을 때,

prefixSum[i] - prefixSum[j]는 j+1부터 i까지의 부분 배열의 합이 됩니다.

 

어떤 부분 배열 subarray(i, j)가 K로 나누어 떨어지는 조건

(prefixSum[i] - prefixSum[j]) % K = 0

 

즉, prefixSum[i]와 prefixSum[j]의 나머지가 같으면

해당 부분 배열의 합이 k로 나누어 떨어지는 부분 배열이 됩니다.

정답코드

class Solution {
    // 누적합인데
    // prefixSum % k == 0 조건을 만족하는 sol의 갯수

    func subarraysDivByK(_ nums: [Int], _ k: Int) -> Int {
        var sol = 0
        var map = [Int: Int]()
        map[0] = 1

        func recursivePrefixSum(_ curSum: Int, _ curIndex: Int) {
            guard curIndex < nums.count else { return }
            let newSum = curSum + nums[curIndex]

            let remainder = ((newSum % k) + k) % k
            if let value = map[remainder] {
                sol += value
            }

            map[remainder, default: 0] += 1
            recursivePrefixSum(newSum, curIndex + 1)
            map[remainder]! -= 1
        }
        recursivePrefixSum(0,0)
        
        return sol
    }



}

 

 

작게 드는 생각

누적합 관련 문제를 풀 때마다 새로운 이론..? 방법..? 공식..????을 배우게 된다.

알아야하는 유형이 점점 많아진다..