주어진 이진 문자열(binary string)에서 하나의 부분 문자열(substring)을 찾은 뒤, 그 부분 문자열 안에서 0의 개수와 1의 개수 차이가 최대가 되는 값을 구하는 것이 이번 문제의 목표입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력 예제
str = "100100110"
출력
3
설명
위 문자열에서 특정 구간의 부분 문자열 "00100"을 살펴보면, 0은 4개, 1은 1개이므로 개수 차이는 4 − 1 = 3입니다. 이 값이 해당 문자열에서 구할 수 있는 최댓값입니다.
입력 예제
str = "00000"
출력
5
모든 문자가 0으로만 이루어져 있다면, 전체 문자열을 선택했을 때 차이가 문자열 길이와 같아지므로 출력은 5가 됩니다.
풀이 접근 방식
main() 함수에서 이진 문자열을 저장할 string 타입의 str 변수를 생성하고, 문자열의 크기(size)를 저장할 int형 변수를 초기화한 뒤, 두 값을 모두 Max() 함수에 전달합니다.
Max() 함수에서는 가장 먼저 One() 함수를 호출하여 문자열의 모든 요소가 1로만 이루어져 있는지 확인합니다.
bool 타입의 One() 함수를 작성하고, 그 안에 int형 변수 O = 0을 선언합니다.
i = 0부터 i < str.size()까지 반복하면서 str[i] == '1'일 때마다 변수 O에 1을 더합니다.
반복문이 끝난 뒤 if(O == size) 조건을 검사하여, 참이면 true를 반환합니다.
다시 Max() 함수로 돌아와, One() 함수가 true를 반환했다면 0과 1의 차이를 계산할 수 없으므로 -1을 답으로 반환합니다.
그렇지 않다면 실제 최대 차이를 계산합니다. 먼저 int a[100] = { 0 } 배열을 초기화합니다.
i = 0부터 i < size까지 반복하면서 a[i] = (str[i] == '0' ? 1 : -1)로 설정해 문자열의 각 문자를 숫자 값으로 변환합니다. 즉, '0'은 1로, '1'은 -1로 매핑됩니다.
반복문 밖에서 int arr[100][3] 배열을 선언하고, memset(arr, -1, sizeof arr)을 사용해 모든 요소를 -1로 초기화한 후, 최종적으로 Length(a, str, size, 0, 0, arr)를 호출합니다.
Length() 함수에서는 먼저 (i >= size)인지 확인합니다. 참이라면 문자열을 모두 검사했다는 의미이므로 0을 반환합니다.
다음으로 (arr[i][s] != -1)인지 확인합니다. 참이라면 해당 상태가 이미 계산되었다는 의미이므로 저장된 값 arr[i][s]를 그대로 반환합니다. 이것이 바로 중복 계산을 방지하는 메모이제이션(memoization) 기법입니다.
이후 (s == 0)인지 확인합니다. 참이라면 새로운 부분 문자열을 시작할 수 있으므로 arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), Length(a, str, size, i + 1, 0, arr))를 반환합니다.
s == 0이 아니라면 현재 진행 중인 부분 문자열을 계속 확장하거나 중단할 수 있으므로, arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), 0)을 반환합니다.
구현 예제 코드
#include <bits/stdc++.h>
using namespace std;
bool One(string str, int size){
int O = 0;
for (int i = 0; i < str.size(); i++)
O += (str[i] == '1');
return (O == size);
}
int Length(int a[], string str, int size,
int i, int s, int arr[][3]){
// 문자열이 끝난 경우
if (i >= size)
return 0;
// 이미 계산된 상태인 경우
if (arr[i][s] != -1)
return arr[i][s];
if (s == 0)
return arr[i][s] = max(a[i] +
Length(a, str, size, i + 1, 1, arr),
Length(a, str, size, i + 1, 0, arr));
else
return arr[i][s] = max(a[i] +
Length(a, str, size, i + 1, 1, arr), 0);
}
int Max(string str, int size){
// 모든 요소가 1인지 확인
if (One(str, size))
return -1;
// 최대 길이(차이) 계산
int a[100] = { 0 };
for (int i = 0; i < size; i++)
a[i] = (str[i] == '0' ? 1 : -1);
int arr[100][3];
memset(arr, -1, sizeof arr);
return Length(a, str, size, 0, 0, arr);
}
// main 함수
int main(){
string str = "100100110";
int size = 9;
cout << Max(str, size);
return 0;
}출력 결과
3
이 풀이는 각 문자를 '0'이면 1로, '1'이면 -1로 변환한 뒤, 최대 부분 배열 합(Kadane 알고리즘과 유사한 아이디어)을 재귀와 메모이제이션으로 구한 것과 같습니다. 덕분에 동일한 상태를 반복 계산하지 않아 효율적으로 답을 구할 수 있습니다.