Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 문자열에서 “1(0+)1” 패턴 발생 횟수 구하기

문제 개요

0과 1, 그리고 그 외의 문자들이 섞여 있는 문자열 str이 주어졌다고 가정해 봅시다. 이 문자열에는 “1(0+)1” 형태의 패턴이 포함되어 있으며, 여기서 0+는 하나 이상(>0)의 연속된 0을 의미합니다. 목표는 문자열 str 안에서 이러한 패턴이 총 몇 번 등장하는지 세는 것입니다.

예제로 살펴보기

예제 1

  • 입력: str = “abb010bb10111011”
  • 출력: 문자열에서 “1(0+)1” 패턴의 발생 횟수 − 2
  • 설명: “abb010bb1011011” 부분에서 패턴이 두 번 발견됩니다.

예제 2

  • 입력: str = “01001011001001100”
  • 출력: 문자열에서 “1(0+)1” 패턴의 발생 횟수 − 4
  • 설명: 발견된 패턴은 각각 “1001”, “101”, “1001”, “1001”로 총 네 번입니다.

풀이 접근 방식

핵심 관찰은 모든 패턴이 1로 시작하여 1로 끝난다는 점입니다. 이를 활용해 첫 번째 1을 플래그 변수(check = 1)로 표시한 뒤 그 사이의 0들은 건너뜁니다. 그러다 또 다른 1을 만났을 때 플래그가 여전히 1이라면 두 1 사이에 0이 있었는지 확인하고, 직전 문자가 0이었다면 패턴이 성립한 것이므로 카운트를 증가시킵니다. 반면 0도 1도 아닌 다른 문자가 등장하면 해당 위치는 패턴에 포함될 수 없으므로 플래그를 다시 0으로 초기화합니다.

구체적인 알고리즘은 다음과 같습니다.

  1. 문자열 str을 입력받습니다.
  2. Pattern_occurrences(string str, int length) 함수는 문자열과 그 길이를 인자로 받아 “1(0+)1” 패턴의 발생 횟수를 반환합니다.
  3. 카운트(count)를 0으로, 플래그 변수(check)를 0으로 초기화합니다.
  4. for 반복문으로 인덱스 i = 0부터 i < length까지 str을 순회합니다.
  5. 현재 문자 str[i]가 ‘1’이고 check가 0이라면 check를 1로 설정한 뒤 계속 진행합니다. (패턴의 시작)
  6. 현재 문자 str[i]가 ‘1’이고 check가 1이라면 두 번째 1입니다. 직전 값 str[i-1]이 ‘0’인지 확인하고, 맞다면 두 1 사이에 0이 존재하는 것이므로 패턴이 발견된 것이며 count를 증가시킵니다.
  7. 현재 문자가 0도 1도 아니라면 해당 문자는 절대 패턴에 속하지 않으므로 check를 0으로 되돌립니다. 이후 다시 만나는 1은 새로운 패턴의 시작(존재한다면)으로 간주됩니다.
  8. 순회가 끝나면 count에는 str 안의 패턴 개수가 저장되어 있습니다.
  9. count를 결과로 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int Pattern_occurrences(string str, int length){
    int count = 0;
    bool check = 0;
    for (int i = 0; i < length ; i++){
       if (str[i] == '1' && check == 1){
          if (str[i - 1] == '0'){
             count++;
          }
       }
       if (str[i] == '1' && check == 0){
          check = 1;
          continue;
       }
       if (str[i] != '0' && str[i] != '1'){
          check = 0;
       }
    }
    return count;
}
int main(){
    string str = "01010111011";
    int length = str.length();
    cout<<"Count of occurrences of a \"1(0+)1\" pattern in a string are: "<< Pattern_occurrences(str, length);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of occurrences of a "1(0+)1" pattern in a string are: 3

시간 복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 별도의 배열이나 자료구조 없이 플래그 변수와 카운터만 사용하므로 공간 복잡도는 O(1)입니다. 문자열의 길이와 무관하게 선형 시간에 동작하기 때문에 매우 효율적입니다.

마무리

플래그 변수 하나로 이전 상태를 추적하는 간단한 아이디어 덕분에, 정규표현식이나 별도의 파싱 로직 없이도 선형 시간에 “1(0+)1” 패턴의 개수를 셀 수 있습니다. 특정 하위 패턴 검출이나 상태 기반 문자열 스캔 유형의 문제에도 동일한 접근 방식을 응용할 수 있으니 참고해 보시기 바랍니다.