leetcode - 974. Subarray Sums Divisible by K

 

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

Subarray Sums Divisible by K - LeetCode

 

이 문제는 구간합 % K 가 0 이되는 구간을 모두 구하는 문제입니다.

 

이 문제는 배열 내에 음수가 존재하기 때문에 슬라이딩 윈도우로 구간합을 구하기 충분하지 않습니다.

그래서 다른 방식을 이용해서 문제를 해결해야 합니다. 

 

 

 

 

문제를 다시 정의해보면,
Sum(i)를 0번 인덱스부터 i번 인덱스까지의 누적합이라고 할 때,
우리가 구해야 하는 것은 다음 조건을 만족하는 (i, j) 쌍의 개수입니다.

 

 

(Sum(i) - Sum(j)) % k == 0

여기서 Sum(i) - Sum(j)는 결국 어떤 구간의 합을 의미하므로,
이 문제는 곧 합이 k로 나누어떨어지는 부분 배열의 개수를 구하는 문제라고 볼 수 있습니다.

 

처음에는 Prefix Sum을 구한 뒤, 모든 (i, j) 쌍을 이중 반복문으로 확인할 수도 있습니다.
하지만 배열의 길이가 최대 3 * 10^4이므로, 이런 방식은 O(n^2)가 되어 비효율적입니다.

 

 

그래서 식을 다시 보면,

(Sum(i) - Sum(j)) % k == 0

이라는 조건은 곧

Sum(i) % k == Sum(j) % k

와 동치입니다.

즉, 두 누적합을 k로 나눈 나머지가 같다면,

그 사이 구간의 합은 k로 나누어떨어집니다.

따라서 배열을 왼쪽부터 순회하면서 현재까지의 누적합 Sum(i)를 구하고,
이 값을 k로 나눈 나머지를 계산합니다.
그다음, 이전까지 등장했던 누적합 나머지 값들 중 현재와 같은 값의 개수만큼
조건을 만족하는 부분 배열이 새롭게 만들어집니다.

이를 위해 Map을 사용해
각 나머지 값이 몇 번 등장했는지를 저장합니다.

• Key: Sum % k
• Value: 해당 나머지가 나온 횟수

정리하면 알고리즘은 다음과 같습니다.

1. 배열을 순회하며 누적합을 구한다.
2. 현재 누적합을 k로 나눈 나머지를 구한다.
3. 이전에 같은 나머지가 몇 번 나왔는지 확인한다.
4. 그 개수를 정답에 더한다.
5. 현재 나머지의 등장 횟수를 Map에 기록한다.

 

코드

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int sum = 0;
        int ans = 0;

        for(int x : nums){
            sum += x;

            int curK = ((sum % k) + k) % k;
            if(curK == 0) ans++;
            if(map.containsKey(curK)) ans += map.get(curK);

            map.put(curK, map.getOrDefault(curK,0) + 1);
        }

        return ans;
    }
}