C++로 숫자 문자열에서 짝수 부분 문자열 개수 구하기

숫자로만 이루어진 문자열이 주어졌을 때, 그 안에서 만들 수 있는 짝수 부분 문자열의 개수를 구하는 문제입니다. 예제를 통해 살펴보겠습니다.

입력

num = "1234"

출력

6

주어진 문자열에서 만들 수 있는 짝수 부분 문자열은 다음과 같습니다.

2
12
4
34
234
1234

핵심 아이디어

어떤 수가 짝수인지 아닌지는 오직 마지막 자릿수에 의해서만 결정됩니다. 따라서 특정 위치의 숫자가 짝수라면, 그 위치를 끝으로 하는 모든 부분 문자열은 반드시 짝수가 됩니다. 인덱스 i(0부터 시작)에 있는 숫자가 짝수일 때, 그 위치를 끝으로 하는 부분 문자열은 정확히 i + 1개 존재합니다. 이 성질을 활용하면 문자열을 한 번만 순회하여 O(n) 시간에 답을 구할 수 있습니다.

알고리즘

• 숫자로 이루어진 문자열을 준비합니다.

• 카운트 변수를 0으로 초기화합니다.

• 문자열을 처음부터 끝까지 순회합니다.

  • 현재 문자에서 문자 '0'을 빼서 실제 숫자 값을 구합니다.

  • 해당 숫자가 짝수인지 확인합니다.

  • 현재 숫자가 짝수라면, 현재 인덱스에 1을 더한 값(i + 1)을 카운트에 누적합니다.

• 최종 카운트를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include<bits/stdc++.h>
using namespace std;
int getEvenSubstringsCount(char str[]) {
    int len = strlen(str), count = 0;
    for (int i = 0; i < len; i++) {
        int currentDigit = str[i] - '0';
        if (currentDigit % 2 == 0) {
            count += i + 1;
        }
    }
    return count;
}
int main() {
    char str[] = "12345678";
    cout << getEvenSubstringsCount(str) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

20

"12345678"에서 짝수인 숫자는 2, 4, 6, 8이며, 각각 인덱스 1, 3, 5, 7에 위치합니다. 따라서 답은 (1+1) + (3+1) + (5+1) + (7+1) = 2 + 4 + 6 + 8 = 20이 됩니다.

복잡도 분석

문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.