문자열 'str'의 길이와 문자열을 지정했다고 가정해 보겠습니다. 작업은 주어진 이진 문자열에서 '1'로 시작하고 '1'로 끝나는 부분 문자열의 수를 계산하는 것입니다. 이진 문자열에는 '1'과 '0'만 포함됩니다. 예를 들어,
입력-1 -
N = 5 str = ‘11101’
출력 -
6
설명 − 주어진 Binary String에는 '1'로 시작하고 '1'로 끝나는 6개의 부분 문자열이 있습니다. 이러한 부분 문자열의 집합은 {'11', '111', '1110', '11101', '1101', '101'}입니다.
입력-1 -
N = 4 str = ‘0011’
출력 -
1
설명 -
주어진 이진 문자열에는 '1'로 시작하고 '1'로 끝나는 1개의 하위 문자열이 있습니다. 이 부분 문자열의 집합은 단일 집합, 즉 { '11 '}입니다.
이 문제를 해결하기 위해 사용된 접근 방식
주어진 문자열에 대해 '1'로 시작하고 '1'로 끝나는 부분 문자열의 수를 계산해야 합니다. 이 문제는 'n'명의 파티에서 핸드셰이크 횟수를 계산해야 하는 잘 알려진 핸드셰이크 문제와 유사합니다.
주어진 문자열에서 1의 개수를 세면 '1'로 시작하고 '1'로 끝나는 부분 문자열 집합을 찾을 수 있습니다.
-
N 길이의 문자열을 입력하십시오.
-
정수 함수 countSubstring(int N, string s)은 문자열의 길이와 문자열을 입력으로 받아 '1'로 시작하고 '1'로 끝나는 모든 부분 문자열의 개수를 반환합니다.
-
전체 문자열을 반복하고 숫자를 세십시오. 문자열의 '1' 중.
-
번호를 계산합니다. n*(n-1)/2로 주어진 문자열의 하위 문자열(쌍)의
-
n*(n-1)/2의 결과를 반환합니다.
예시
#include<iostream>
using namespace std;
int countSubstring(int N, string s){
int count=0;
for(int i=0; s[i]!= '\0'; ++i){
if( s[i]== '1' )
count++;
}
return count*(count-1)/2;
}
int main() {
int N=5;
string str= "11101";
cout<< countSubstring(N,str)<<endl;
return 0;
} 출력
위의 코드를 실행하면 출력이 다음과 같이 인쇄됩니다.
6
주어진 문자열에 존재하는 '1'의 개수는 '4' 즉 count =4이므로 '1'로 시작하여 '1'로 끝나는 부분 문자열의 총 개수는 4*(4-1)/2입니다. =6.