C++에서 ASCII 값의 합이 k로 나누어 떨어지는 길이 k 부분 문자열 개수 구하기

문자열과 하나의 정수 k가 주어졌을 때, 길이가 정확히 k인 모든 부분 문자열 가운데 문자들의 ASCII 값 합이 k로 나누어 떨어지는 것의 개수를 구하는 문제를 풀어보겠습니다.

예를 들어 문자열이 "BCGABC"이고 k가 3이라고 가정해 보겠습니다. 부분 문자열 "BCG"의 ASCII 합은 204('B'=66, 'C'=67, 'G'=71)이고, "ABC"의 ASCII 합은 198('A'=65, 'B'=66, 'C'=67)입니다. 두 값 모두 k=3으로 나누어 떨어지므로 조건을 만족하는 부분 문자열은 총 2개입니다.

접근 방법

풀이 방법은 간단합니다. 먼저 첫 번째 부분 문자열, 즉 앞에서부터 k개 문자의 ASCII 값을 모두 더해 초기 합을 구합니다. 이후 슬라이딩 윈도우(sliding window) 기법을 활용하는데, 윈도우를 한 칸씩 오른쪽으로 밀 때마다 빠져나가는 맨 앞 문자의 ASCII 값은 빼고 새로 들어오는 문자의 ASCII 값은 더해주면 됩니다. 매 단계마다 현재 합이 k로 나누어 떨어지는지 확인하고, 나누어 떨어진다면 카운트를 1 증가시킵니다.

이 방식은 각 부분 문자열의 합을 처음부터 다시 계산하지 않고 이전 합을 재활용하기 때문에, 전체 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

#include <iostream>
using namespace std;

int countKLenSubstr(string str, int k) {
    int len = str.length();
    int sum = 0;
    int count = 0;

    // 첫 번째 부분 문자열(길이 k)의 ASCII 합 계산
    for (int i = 0; i < k; i++)
        sum += str[i];

    if (sum % k == 0)
        count++;

    // 슬라이딩 윈도우로 나머지 부분 문자열 검사
    for (int i = k; i < len; i++) {
        sum -= str[i - k]; // 윈도우에서 빠지는 문자의 ASCII 값 제거
        sum += str[i];     // 새로 들어오는 문자의 ASCII 값 추가
        if (sum % k == 0)
            count++;
    }
    return count;
}

int main() {
    string s = "BCGABC";
    int k = 3;
    cout << "조건을 만족하는 부분 문자열의 개수: " << countKLenSubstr(s, k);
    return 0;
}

실행 결과

조건을 만족하는 부분 문자열의 개수: 2

마무리

이처럼 슬라이딩 윈도우 기법을 사용하면 길이가 k인 모든 부분 문자열을 일일이 순회하며 합을 새로 구하는 비효율적인 O(n×k) 방식 대신, O(n) 시간 안에 문제를 해결할 수 있습니다. 누적된 합을 갱신하며 최적화하는 이 패턴은 부분 배열이나 부분 문자열 관련 알고리즘 문제에서 자주 등장하는 핵심 기법이므로 잘 익혀두면 큰 도움이 됩니다.