C++로 이진 문자열에서 '010' 패턴을 제거하는 최소 단계 구하기

문제 설명

이진 문자열(0과 1로만 이루어진 문자열)이 주어졌을 때, 문자열 내에 존재하는 부분 문자열 "010" 패턴을 모두 제거하기 위해 필요한 최소 변경 횟수를 구하는 것이 이번 문제의 목표입니다.

여기서 '제거'란 문자열에서 문자를 삭제하는 것이 아니라, 특정 문자를 다른 문자로 변경하여 "010" 패턴이 더 이상 나타나지 않도록 만드는 것을 의미합니다.

예시

입력 문자열이 "010010"이라면 총 2단계가 필요합니다.

첫 번째 '0'을 '1'로 변경합니다. → 문자열은 "110010"이 됩니다.
마지막 '0'을 '1'로 변경합니다. → 최종 문자열은 "110011"이 됩니다.

최종 문자열에는 더 이상 "010" 패턴이 존재하지 않으므로, 최소 2번의 변경으로 목표를 달성할 수 있습니다.

알고리즘

핵심 아이디어는 간단합니다. "010" 패턴을 발견하면 세 문자 중 단 하나만 변경해도 해당 패턴은 깨집니다. 따라서 패턴을 찾으면 단계 수를 1 증가시키고, 이미 처리한 구간과 겹치지 않도록 인덱스를 건너뛰면 됩니다.

인덱스 0부터 n-3까지 문자열을 순회합니다.
현재 위치에서 연속된 세 문자가 '0', '1', '0'이라면 단계 수(cnt)를 1 증가시킵니다.
패턴을 발견한 경우 루프 인덱스를 2만큼 추가로 건너뛰어, 같은 문자를 중복해서 처리하지 않도록 합니다.

이렇게 하면 겹치는 패턴(예: "01010")도 한 번의 변경으로 해결되는 경우를 정확하게 계산할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int getMinSteps(string str) {
    int cnt = 0;
    for (int i = 0; i < str.length() - 2; ++i) {
        if (str[i] == '0' && str[i + 1] == '1' && str[i + 2] == '0') {
            ++cnt;
            i += 2; // 이미 처리한 패턴 구간 건너뛰기
        }
    }
    return cnt;
}

int main() {
    string str = "010010";
    cout << "Minimum required steps = " << getMinSteps(str)
         << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Minimum required steps = 2

복잡도 분석

시간 복잡도: O(n) — 문자열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 추가적인 메모리 없이 카운터 변수만 사용합니다.

이처럼 슬라이딩 윈도우 방식으로 문자열을 훑으며 패턴 발견 시 인덱스를 점프하는 기법은, 선형 시간 안에 최소 변경 횟수를 효율적으로 구할 수 있는 대표적인 그리디(Greedy) 접근 방식입니다.