0과 1로만 구성된 문자열이 주어집니다. 이 문자열은 왼쪽에서 오른쪽으로 읽는 이진수를 나타내며, 맨 앞 문자가 최하위 비트(LSB)입니다. 예를 들어 "001"은 1이 아니라 4에 해당합니다. 우리의 목표는 십진수로 변환했을 때 짝수가 되는 모든 부분 문자열의 개수를 구하는 것입니다.
핵심 아이디어는 매우 간단합니다. 각 부분 문자열의 첫 번째 문자만 확인하면 됩니다. 첫 문자가 '0'이면 해당 부분 문자열이 나타내는 십진 값은 반드시 짝수이고, '1'이면 홀수입니다. 따라서 str[i]가 '0'인 인덱스 i에서 시작하는 부분 문자열은 모두 (length - i)개이며, 카운트를 이만큼 증가시키면 전체 개수를 효율적으로 구할 수 있습니다.
예시를 통해 자세히 살펴보겠습니다.
입력 − str="101"
출력 − 이진 문자열에서 짝수 십진 값을 갖는 부분 문자열의 개수: 2
설명 − 가능한 부분 문자열은 10, 11, 01, 0, 1이며, 이 중 01(십진 값 2)과 0(십진 값 0), 총 2개가 짝수입니다.
입력 − str="111"
출력 − 이진 문자열에서 짝수 십진 값을 갖는 부분 문자열의 개수: 0
설명 − 가능한 부분 문자열은 11, 1뿐이며, 이 중 짝수는 하나도 없습니다.
프로그램에서 사용된 접근 방식
0과 1로만 이루어진 문자열 str을 입력받습니다.
문자열의 길이를 len = str.length()로 저장합니다.
count_even(string str, int length) 함수는 문자열과 그 길이를 받아 짝수 십진 값을 만드는 부분 문자열의 개수를 반환합니다.
FOR 루프를 사용해 문자열을 순회합니다.
인덱스 i = 0부터 i < len까지, 왼쪽에서 오른쪽 방향으로 이진수를 읽습니다.
str[i] == '0'이면 해당 위치에서 시작하는 모든 부분 문자열의 십진 값은 짝수입니다.
카운트를 (length - i)만큼 증가시킵니다.
누적된 카운트를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int count_even(string str, int length){
int count = 0;
for (int i = 0; i < length; i++){
if (str[i] == '0'){
count += (length - i);
}
}
return count;
}
int main(){
string str = "00111";
int len = str.length();
cout<<"Count of even decimal value substrings in a binary string are: "<<count_even(str, len) << endl;
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of even decimal value substrings in a binary string are: 9