문제 정의
길이가 n인 이진(binary) 문자열과 정수 k가 주어집니다. 이진 문자열을 k번 반복해 이어 붙인(concatenate) 새로운 문자열을 만든 뒤, 그 안에서 연속된 0의 최대 개수를 구하는 것이 이 문제의 목표입니다.
예를 들어 이진 문자열이 "0010010"이고 k = 2라고 가정해 보겠습니다. 문자열을 두 번 이어 붙이면 "00100100010010"이 되며, 이 문자열에서 연속된 0의 최대 길이는 3입니다.
해결 아이디어
접근 방법은 의외로 간단합니다. 문자열을 실제로 k번 복제하지 않아도, 원본 문자열만 분석하면 정답을 구할 수 있습니다.
- 문자열 전체가 0으로만 이루어진 경우: 정답은 n × k입니다.
- 문자열에 1이 하나라도 포함된 경우: 정답은 다음 두 값 중 더 큰 값입니다.
- 원본 문자열 내부에 있는 0으로만 구성된 부분 문자열의 최대 길이
- 0으로만 이루어진 최대 접두사(prefix)의 길이 + 0으로만 이루어진 최대 접미사(suffix)의 길이
접두사와 접미사의 합을 고려하는 이유는, 문자열을 이어 붙일 때 앞쪽의 0과 뒤쪽의 0이 서로 만나 더 긴 연속 0 구간을 형성할 수 있기 때문입니다.
알고리즘
max_zero_count(str, n, k)
시작 total := 0 len := 0 for i from 0 to n: if str[i] = 0, then len 증가 else len := 0 total := max(total, len) end for if total = n, then return n * k // 문자열 전체가 0인 경우 prefix := 0으로만 이루어진 최대 접두사의 길이 suffix := 0으로만 이루어진 최대 접미사의 길이 if k > 1, then total := max(total, prefix + suffix) return total 종료
C++ 예제 코드
#include <iostream>
using namespace std;
int max_length_substring(string str, int n, int k) {
int total_len = 0;
int len = 0;
for (int i = 0; i < n; ++i) {
if (str[i] == '0') // 현재 문자가 0이면 len 증가
len++;
else
len = 0;
total_len = max(total_len, len);
}
if (total_len == n) // 문자열 전체가 0으로만 이루어진 경우
return n * k;
int prefix = 0, suffix = 0;
for (int i = 0; str[i] == '0'; ++i, ++prefix); // 0으로만 이루어진 최대 접두사의 길이
for (int i = n - 1; str[i] == '0'; --i, ++suffix); // 0으로만 이루어진 최대 접미사의 길이
if (k > 1)
total_len = max(total_len, prefix + suffix);
return total_len;
}
int main() {
int k = 3;
string str = "0010010";
int res = max_length_substring(str, str.length(), k);
cout << "Maximum length of 0s: " << res;
}
실행 결과
Maximum length of 0s: 3
시간 복잡도
이 알고리즘은 문자열을 한 번 순회하며 최대 연속 0의 길이를 구하고, 접두사와 접미사의 길이를 확인하는 과정 역시 선형 시간 안에 처리됩니다. 따라서 전체 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 문자열을 실제로 k번 이어 붙이지 않고 원본만 분석하기 때문에, k가 매우 커지더라도 효율적으로 동작한다는 점이 이 풀이의 핵심 장점입니다.