C++로 푸는 연속 부분 배열 합 문제: k의 배수 판별 알고리즘

문제 개요

음수가 아닌 정수로 이루어진 배열과 목표 정수 k가 주어졌을 때, 크기가 최소 2 이상인 연속 부분 배열의 합이 k의 배수(즉, n × k, 여기서 n도 정수)가 되는 경우가 존재하는지 판별하는 함수를 작성해야 합니다.

예를 들어 입력 배열이 [23, 2, 4, 6, 7]이고 k = 6이라면 결과는 참(True)입니다. 부분 배열 [2, 4]의 크기는 2이며, 그 합이 6으로 k의 배수이기 때문입니다.

핵심 아이디어: 누적 합과 나머지 연산

이 문제는 누적 합(prefix sum)과 모듈로 연산의 성질을 활용하면 선형 시간 안에 해결할 수 있습니다.

두 지점 i와 j(i < j)에서의 누적 합을 각각 S(i), S(j)라고 할 때, 두 값을 k로 나눈 나머지가 서로 같다면 구간 (i, j]의 합은 반드시 k의 배수가 됩니다. 따라서 해시 맵에 각 나머지 값이 처음 등장한 인덱스를 기록해 두고, 같은 나머지가 다시 나타났을 때 두 인덱스의 차이가 2 이상인지만 확인하면 됩니다.

알고리즘 단계

• 맵 m을 생성하고 m[0] := -1로 초기화합니다. 또한 sum := 0, n := 배열 nums의 크기로 설정합니다.
• i를 0부터 n-1까지 반복합니다:
  • sum := sum + nums[i]
  • k가 0이 아니라면 sum := sum mod k
  • m에 sum이 이미 존재하고 i − m[sum] ≥ 2라면 true를 반환합니다.
  • m에 sum이 존재하지 않으면 m[sum] := i로 설정합니다.
• 반복이 모두 끝나면 false를 반환합니다.

m[0] = -1로 초기화하는 이유는 배열의 가장 앞부분부터 시작하는 부분 배열의 경우도 올바르게 처리하기 위함입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool checkSubarraySum(vector<int>& nums, int k) {
      unordered_map<int, int> m;
      m[0] = -1;
      int sum = 0;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         sum += nums[i];
         if(k)
         sum %= k;
         if(m.count(sum) && i - m[sum] >= 2){
            return true;
         }
         if(!m.count(sum)) m[sum] = i;
      }
      return false;
   }
};
main(){
   vector<int> v = {23,2,4,6,7};
   Solution ob;
   cout << (ob.checkSubarraySum(v, 6));
}

입력

[23,2,4,6,7]
6

출력

1

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번만 순회하며 각 원소마다 상수 시간의 해시 맵 연산을 수행합니다.
공간 복잡도: O(min(n, k)) — 해시 맵에는 서로 다른 나머지 값들만 저장되므로 최대 min(n, k)개의 항목을 가집니다.