C++로 이진 문자열에서 0과 1 개수의 최대 차이 구하기 (O(n) 시간 복잡도)

주어진 이진 문자열에서 부분 문자열(substring)을 찾아, 그 안에서 0의 개수와 1의 개수 차이가 최대가 되는 값을 구하는 문제입니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력 예제

str = "10010110"

출력 결과

설명

위 문자열에서 위치 1부터 4까지의 부분 문자열은 "0010"입니다. 이 구간에서 0은 3개, 1은 1개이므로 차이는 3 − 1 = 2가 되며, 이것이 구할 수 있는 최댓값입니다.

추가 입력 예제

str = "00000"

모든 문자가 0인 경우, 전체 문자열을 선택하면 0과 1의 개수 차이는 5 − 0 = 5로 최대가 됩니다.

해결 접근 방식

main() 함수에서 이진 문자열을 저장할 string 변수 str을 선언하고, 누적 차이를 저장할 int 배열 arr[str.length()+1]을 선언합니다.
memset(arr, 0, sizeof(arr))를 사용하여 arr[]의 모든 요소를 0으로 초기화합니다.
j = 1부터 j <= str.length()까지 반복문을 수행합니다.
현재 문자가 '1'이라면, 1의 개수가 늘어나므로 차이가 감소합니다. 따라서 arr[j] = max(arr[j-1] - 1, -1)로 설정하여 음수가 되는 경우 새로 시작하는 것이 더 유리함을 반영합니다.
현재 문자가 '0'이라면, 차이가 증가하므로 arr[j] = max(arr[j-1] + 1, 1)로 설정합니다.
반복문이 끝나면 *max_element(arr+1, arr+str.length()+1)를 사용하여 배열에서 최댓값을 찾아 출력합니다.

이 방식은 카데인 알고리즘(Kadane's Algorithm)과 유사한 원리로 동작합니다. 각 위치에서 누적합이 음수가 되면 해당 지점부터 새로운 부분 문자열을 시작하는 것이 전체 최댓값에 유리하기 때문입니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str = "10010110";
    int arr[str.length()+1];
    memset(arr,0,sizeof(arr));
    for(int j=1;j<=str.length();j++){
        if(str[j-1]=='1')
            arr[j]=max(arr[j-1]-1,-1);
        else
            arr[j]=max(arr[j-1]+1,1);
    }
    cout<<*max_element(arr+1,arr+str.length()+1);
    return 0;
}