이 문제에서는 'a'와 'b'로만 구성된 문자열이 주어지며, 문자열에서 "ab" 패턴이 완전히 사라질 때까지 필요한 연산 횟수를 계산해야 합니다. 여기서 한 번의 연산은 문자열 속의 "ab"를 "bba"로 교체하는 것을 의미합니다. 따라서 먼저 문자열에 "ab"가 포함되어 있는지 확인한 후, 포함되어 있다면 교체 작업을 반복하여 문자열을 'ab'가 없는 상태(ab-free)로 만들어야 합니다.
입력 − str = "ababaa"
출력 − 이진 문자열을 'ab' 프리로 만들기 위한 연산 횟수 − 4
설명 − 문자열에서 "ab" 패턴이 발견될 때마다 이를 "bba"로 교체합니다. 첫 번째 교체 후에는 문자열이 "bbaabaa"가 되고 연산 횟수는 1이 됩니다. 다시 "ab"를 "bba"로 교체하면 연산 횟수는 2가 되고 문자열은 "bbabbaaa"가 됩니다. 이후에도 "ab"가 남아 있어 교체를 계속 진행하면, 모든 "ab"가 제거될 때까지 총 4번의 연산이 필요합니다.
입력 − str = "abaa"
출력 − 이진 문자열을 'ab' 프리로 만들기 위한 연산 횟수 − 1
설명 − 문자열에 "ab" 패턴이 한 번 나타나므로 이를 "bba"로 교체하면 연산 횟수는 1이 되고 문자열은 "bbaaa"가 됩니다. 이 시점에서 문자열은 더 이상 "ab"를 포함하지 않으므로 총 연산 횟수는 1입니다.
프로그램에서 사용된 접근 방식
문자열을 입력받아 길이를 계산한 후, 추가 처리를 위해 함수에 데이터를 전달합니다.
문자열을 'ab' 프리로 만드는 데 필요한 연산 횟수를 저장할 임시 변수 count를 선언합니다.
문자열 길이 + 1 크기의 문자 배열을 생성합니다.
strcpy() 메서드를 사용하여 문자열의 문자들을 배열에 복사합니다.
0부터 문자열 길이까지 FOR 반복문을 시작합니다.
반복문 안에서 arr[len - i - 1]이 'a'인지 검사하고, 참이라면 count에 total 값을 더한 뒤 total을 2배로 만듭니다.
'a'가 아니라면('b'라면) total을 1 증가시킵니다.
count를 반환합니다.
결과를 출력합니다.
알고리즘의 동작 원리
이 알고리즘의 핵심은 문자열을 오른쪽에서 왼쪽으로 탐색한다는 점입니다. 'b'를 만날 때마다 total을 1 증가시켜 지금까지 만난 'b'의 개수를 추적하고, 'a'를 만날 때마다 현재 total 값을 결과에 더한 후 total을 2배로 늘립니다. 이는 교체 연산이 누적될수록 뒤따르는 'a'가 통과해야 하는 유효 'b'의 개수가 두 배씩 증가하기 때문입니다. 이 방식을 사용하면 실제로 문자열을 반복적으로 교체하지 않고도 O(n) 시간 안에 총 연산 횟수를 계산할 수 있습니다.
예제
#include <bits/stdc++.h>
using namespace std;
// 문자열을 'ab' 프리로 만드는 데 필요한 연산 횟수를 계산하는 함수
int operations_ab_free(string str, int len){
int count = 0;
char arr[len + 1];
strcpy(arr, str.c_str());
int total = 0;
// 문자열을 뒤에서부터 앞으로 탐색
for (int i = 0; i < len; i++){
if (arr[len - i - 1] == 'a'){
count = (count + total);
total = (total * 2);
}
else{
total++;
}
}
return count;
}
int main(){
string str = "ababaa";
int length = str.length();
cout<<"'ab' 프리 이진 문자열을 만들기 위한 연산 횟수: "<<operations_ab_free(str, length)<<endl;
return 0;
}
출력
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
'ab' 프리 이진 문자열을 만들기 위한 연산 횟수: 4