문자열에 1(0+)1 형태의 패턴이 포함되어 있다고 가정해 보겠습니다. 여기서 (0+)는 하나 이상의 '0'이 연속해서 등장하는 구간을 의미합니다. 즉, '1'로 시작해 최소 하나의 '0'을 거쳐 다시 '1'로 끝나는 부분 문자열을 모두 찾아야 하며, 패턴끼리 서로 겹쳐 있더라도 각각 세어야 합니다. 입력 문자열은 반드시 이진 문자열일 필요는 없고, 숫자와 소문자만 포함한다고 가정합니다.
예를 들어 문자열이 1101001이라면 다음 두 개의 패턴을 찾을 수 있습니다.
101(인덱스 1~3)1001(인덱스 3~6)
두 패턴은 인덱스 3의 '1'을 공유하므로, 겹치는 패턴 역시 정상적으로 탐지됩니다.
알고리즘 접근 방식
- 문자열의 모든 문자를 처음부터 끝까지 순회합니다.
- 현재 문자가 '0'이고 바로 앞 문자가 '1'이라면, '1' 뒤에서 '0' 구간이 시작된 것이므로 연속된 모든 '0'을 건너뜁니다.
- '0' 구간이 끝난 직후의 문자가 '1'인지 확인합니다. '1'이라면 유효한 1(0+)1 패턴을 하나 발견한 것이므로 카운터를 증가시킵니다.
- 문자열 끝에 도달할 때까지 위 과정을 반복합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int countBinPattern(string main_str) {
char last_char = main_str[0];
int i = 1, counter = 0;
while (i < main_str.size()) {
if (main_str[i] == '0' && last_char == '1') {
while (main_str[i] == '0')
i++;
if (main_str[i] == '1')
counter++;
}
last_char = main_str[i];
i++;
}
return counter;
}
int main() {
string str = "10010110000101";
cout << "Number of substrings of pattern 1(0+)1 is: " << countBinPattern(str);
}
실행 결과
Number of substrings of pattern 1(0+)1 is: 4
코드 설명
- last_char: 이전 문자를 기억하여 '1'에서 '0'으로 전환되는 지점을 감지합니다.
- 내부 while 루프: 연속된 '0'을 한 번에 건너뛰어 불필요한 비교를 제거합니다.
- counter: 발견된 패턴의 총 개수를 저장하며, 함수의 반환값으로 사용됩니다.
각 문자를 최대 한 번씩만 방문하므로 이 알고리즘의 시간 복잡도는 O(n)이며, 추가 메모리 사용량은 O(1)로 매우 효율적입니다.
주의 사항
문자열이 '1' 뒤에 '0'으로 끝나는 경우(예: "10")에는 내부 루프가 문자열 범위를 벗어날 수 있습니다. 실무 코드에서는 내부 루프 조건에 i < main_str.size() 경계 검사를 함께 추가해 주는 것이 안전합니다.