문제 소개
0과 1로만 이루어진 이진 문자열과 정수 k가 주어졌을 때, 정확히 k개의 1을 포함하는 부분 문자열의 개수를 계산하는 것이 이번 문제의 목표입니다.
입력 − string str = '10000100000', k = 2
출력 − K개의 1을 포함하는 이진 문자열의 부분 문자열 개수: 6
설명 − 주어진 문자열에는 1이 두 개(인덱스 0과 5) 존재합니다. 두 1을 모두 포함하는 부분 문자열은 시작 위치를 첫 번째 1 또는 그 앞의 0 중 하나로, 끝 위치를 두 번째 1 또는 그 뒤의 0 중 하나로 선택하는 경우의 수와 같으므로 총 6가지입니다. 즉, 정확히 2개의 1을 가진 부분 문자열은 6개입니다.
입력 − string str = '10000100000', k = 3
출력 − K개의 1을 포함하는 이진 문자열의 부분 문자열 개수: 0
설명 − k가 3으로 주어졌지만 문자열 전체에 1이 2개뿐이므로, 3개의 1을 포함하는 부분 문자열은 존재할 수 없습니다. 따라서 결과는 0이 됩니다.
알고리즘 및 접근 방식
이 문제는 접두사 빈도 배열(prefix frequency array)을 활용하면 O(n) 시간에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 현재 위치까지 등장한 1의 개수가 total_1일 때, 이전 어느 시점의 접두사가 정확히 (total_1 − k)개의 1을 가지고 있었다면, 그 접두사 바로 다음 문자부터 현재 문자까지의 부분 문자열은 정확히 k개의 1을 포함하게 됩니다.
프로그램의 동작 순서는 다음과 같습니다.
0과 1의 조합으로 된 이진 문자열과 정수 변수 k를 입력받습니다.
length() 함수로 문자열의 길이를 구해 이후 처리를 위해 함수에 전달합니다.
조건을 만족하는 부분 문자열 개수를 저장할 count와, 지금까지 등장한 1의 누적 개수를 저장할 total_1을 0으로 초기화하여 선언합니다.
1의 개수별 빈도를 저장할 배열을 문자열 길이 + 1 크기로 선언하고 0으로 초기화한 뒤, 첫 번째 요소를 1로 설정합니다. 이는 1이 0개인 빈 접두사가 하나 존재함을 의미합니다.
for 루프를 0부터 문자열 길이까지 반복합니다.
루프 안에서 total_1 = total_1 + (str[i] - '0')으로 누적 1의 개수를 갱신합니다. 만약 total_1 >= k라면 count에 arr_fre[total_1 - k]를 더합니다.
arr_fre[total_1] 값을 1 증가시켜 현재까지의 1 개수 빈도를 기록합니다.
모든 반복이 끝나면 count를 반환하고 결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 정확히 k개의 1을 포함하는 부분 문자열의 개수를 계산하는 함수
int sub_k_ones(string str, int length, int k){
int count = 0; // 조건을 만족하는 부분 문자열 개수
int total_1 = 0; // 현재 위치까지 등장한 1의 총 개수
int arr_fre[length + 1] = {0}; // 1의 개수별 빈도 저장 배열
arr_fre[0] = 1; // 1이 0개인 접두사는 하나 존재
for (int i = 0; i < length; i++){
total_1 = total_1 + (str[i] - '0'); // 현재 문자가 1이면 누적 개수 증가
if (total_1 >= k){
// (total_1 - k)개의 1을 가진 접두사 개수만큼 유효한 부분 문자열 추가
count = count + arr_fre[total_1 - k];
}
arr_fre[total_1]++; // 현재 1의 개수 빈도 갱신
}
return count;
}
int main(){
string str = "10000100000";
int length = str.length();
int k = 2;
cout<<"Count of substrings of a binary string containing K ones are: "<<sub_k_ones(str, length, k) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of substrings of a binary string containing K ones are: 6
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 빈도 배열에 문자열 길이에 비례하는 공간을 사용하므로 공간 복잡도 역시 O(n)입니다. 모든 부분 문자열을 일일이 검사하는 브루트포스 방식(O(n²) 이상)보다 훨씬 효율적으로 문제를 해결할 수 있다는 점이 이 접근법의 가장 큰 장점입니다.