C++로 이진 문자열에서 '01' 또는 '10' 부분 문자열 삭제하기

문제 소개

이진 문자열(binary string)이 주어졌을 때, "01" 또는 "10" 부분 문자열을 반복해서 삭제하여 문자열 전체에 더 이상 "01"이나 "10"이 존재하지 않도록 만들어야 합니다. 이 문제의 핵심은 수행할 수 있는 최대 삭제 횟수를 구하는 것입니다.

핵심 아이디어

"01" 또는 "10"을 한 번 삭제할 때마다 항상 '0' 하나와 '1' 하나가 동시에 제거됩니다. 따라서 가능한 최대 삭제 횟수는 문자열 안에서 더 적게 등장한 문자의 개수, 즉 min(0의 개수, 1의 개수)와 같습니다.

예를 들어 '0'이 5개, '1'이 6개 있는 문자열이라면 최대 5번 삭제할 수 있으며, 삭제가 끝난 뒤에는 '1' 하나만 남게 됩니다.

알고리즘 구현

먼저 초기 문자열을 선언하고 길이를 계산한 다음, 이를 deleteSubstr(str, length) 함수에 전달합니다.

string str = "01010110011";
int length = str.length();
cout << "Count of substring deletion" << deleteSubstr(str, length);

deleteSubstr(string str, int length) 함수 내부에서는 for 루프가 i가 length보다 작은 동안 실행되며, 문자 '0'을 만나면 count_0 변수를, '1'을 만나면 count_1 변수를 증가시킵니다. 루프가 끝나면 두 카운트 중 작은 값을 반환합니다.

int deleteSubstr(string str, int length){
    int count_0 = 0, count_1 = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == '0')
            count_0++;
        else
            count_1++;
    }
    return min(count_0, count_1);
}

전체 예제 코드

다음은 이진 문자열에서 "01" 또는 "10"을 삭제하여 해당 패턴이 남지 않도록 만드는 전체 구현입니다.

#include <iostream>
using namespace std;
int deleteSubstr(string str, int length){
    int count_0 = 0, count_1 = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == '0')
            count_0++;
        else
            count_1++;
    }
    return min(count_0, count_1);
}
int main(){
    string str = "01010110011";
    int length = str.length();
    cout << "Count of substring deletion " << deleteSubstr(str, length);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of substring deletion 5

결과 분석

입력 문자열 "01010110011"에는 '0'이 5개, '1'이 6개 포함되어 있습니다. 따라서 min(5, 6) = 5번의 삭제가 가능하며, 모든 삭제가 완료된 후 문자열에는 '1' 하나만 남게 됩니다. 이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.