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

문제 개요

n개의 숫자로 이루어진 문자열 S가 주어졌을 때, 부분 문자열이 나타내는 숫자가 짝수라면 그 부분 문자열을 '짝수 부분 문자열'이라고 정의합니다. 우리의 목표는 문자열 S에서 짝수 부분 문자열의 총 개수를 구하는 것입니다.

예를 들어, 입력이 S = "1234"라고 가정해 보겠습니다. 이 경우 출력값은 6이며, 해당되는 부분 문자열은 2, 4, 12, 34, 234, 1234입니다.

접근 방법

이 문제의 핵심 아이디어는 매우 간단합니다. 어떤 수가 짝수이려면 반드시 마지막 자릿수가 짝수여야 합니다. 즉, 부분 문자열이 짝수인지 판단할 때는 시작 위치와 상관없이 끝자리 숫자만 확인하면 됩니다.

따라서 다음과 같은 논리로 문제를 해결할 수 있습니다.

문자열의 각 위치를 왼쪽에서 오른쪽으로 탐색합니다.
현재 위치의 숫자가 짝수라면, 이 숫자를 마지막 자릿수로 가지는 모든 부분 문자열은 짝수입니다.
인덱스 i(0부터 시작)에서 끝나는 부분 문자열의 개수는 정확히 i+1개이므로, 결과값에 i+1을 더해줍니다.
모든 위치를 탐색한 후 누적된 값을 반환합니다.

이 방법은 시간 복잡도 O(n)으로, 문자열 길이에 비례하는 단 한 번의 순회만으로 답을 구할 수 있어 매우 효율적입니다.

알고리즘 단계

결과를 저장할 변수 a를 0으로 초기화합니다.
n을 문자열 S의 길이로 설정합니다.
i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
S[i]를 2로 나눈 나머지가 0(즉, 짝수)이라면 a에 i+1을 더합니다.
반복이 종료되면 a를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int solve(string S){
   int a = 0;
   int n = S.size();
   for (int i = 0; i < n; i++){
      if (S[i] % 2 == 0){
         a += i + 1;
      }
   }
   return a;
}
int main(){
   string S = "1234";
   cout << solve(S) << endl;
}

입력

출력

동작 원리 상세 분석

"1234"를 예로 들어 코드의 실행 과정을 하나씩 살펴보겠습니다.

i = 0: '1'은 홀수이므로 건너뜁니다. (a = 0)
i = 1: '2'는 짝수이므로 a에 2(=1+1)를 더합니다. 여기에는 "12", "2" 두 개의 부분 문자열이 포함됩니다. (a = 2)
i = 2: '3'은 홀수이므로 건너뜁니다. (a = 2)
i = 3: '4'는 짝수이므로 a에 4(=3+1)를 더합니다. 여기에는 "1234", "234", "34", "4" 네 개의 부분 문자열이 포함됩니다. (a = 6)

최종 결과는 6이며, 이는 앞서 직접 나열한 짝수 부분 문자열의 개수와 정확히 일치합니다. 이처럼 끝자리 숫자만 확인하면 되기 때문에 복잡한 부분 문자열 생성 없이도 선형 시간 안에 정답을 구할 수 있습니다.