문제 설명
문자열 S가 주어지며, 각 문자는 '0', '1' 또는 '?' 중 하나입니다. 우리는 '?'를 각각 0 또는 1로 치환하여 새로운 문자열 T를 만들려고 합니다.
여기서 T의 불균형(unbalancedness)은 다음과 같이 정의됩니다. 0 ≤ l ≤ r < |S|를 만족하는 모든 구간 [l, r]에 대해, 해당 구간 안에서 0의 개수와 1의 개수 차이의 절댓값을 계산하고, 그 값들 중 최댓값을 불균형이라고 합니다. 목표는 '?'를 적절히 채워 T가 가질 수 있는 최소 불균형을 찾는 것입니다.
예를 들어 입력이 S = "0??0"이라면, 출력은 2가 됩니다.
해결 접근 방법
이 문제는 이분 탐색(binary search)을 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "불균형 값이 x 이하가 되도록 문자열을 채우는 것이 가능한가?"를 판단하는 함수 check()를 만들고, 가능한 x의 최솟값을 이분 탐색으로 찾는 것입니다.
check(S, x) 함수의 동작 원리
check 함수는 변수 L과 R을 사용합니다. L과 R은 문자열을 왼쪽부터 읽어 나갈 때, 지금까지의 균형 값(1의 개수 − 0의 개수)이 가질 수 있는 범위의 하한과 상한을 의미합니다.
- '0'을 만나면 어떤 선택을 하더라도 균형 값이 1 감소하므로 L과 R을 모두 1씩 줄입니다.
- '1'을 만나면 반대로 L과 R을 모두 1씩 늘립니다.
- '?'를 만나면 0 또는 1 중 자유롭게 선택할 수 있으므로 가능 범위가 넓어집니다. 즉, L은 1 감소하고 R은 1 증가합니다. 단, L과 R이 같아지는 순간 플래그 B를 false로 설정합니다.
B 플래그는 "아직 '?' 선택의 여유가 있는지"를 추적합니다. R이 허용치 x + 1을 초과하거나 L이 음수가 되면, B 값에 따라 범위를 1칸 또는 2칸 조정해 불균형 한도를 유지합니다. 만약 조정 후에도 L > R이 된다면, 그러한 채우기 방식은 불가능하므로 false를 반환합니다.
메인 로직: 이분 탐색
solve 함수에서는 x의 탐색 범위를 1부터 1,000,000으로 잡고 이분 탐색을 수행합니다. check(S, Mid)가 true이면 더 작은 값도 가능하므로 상한을 줄이고, false이면 하한을 올립니다. 최종적으로 R + 1이 최소 불균형 값이 됩니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool check(string S, int x) {
int L = 0, R = x;
bool B = true;
for (int i = 0; i < S.size(); i++) {
if (S[i] == '0')
L--, R--;
if (S[i] == '1')
L++, R++;
if (S[i] == '?') {
if (L == R)
B = false;
L--;
R++;
}
if (R == x + 1) {
if (B)
R--;
else
R -= 2;
}
if (L < 0) {
if (B)
L++;
else
L += 2;
}
if (L > R)
return false;
}
return true;
}
int solve(string S) {
int L = 1, R = 1000000;
while (L <= R) {
int Mid = L + R >> 1;
if (check(S, Mid))
R = Mid - 1;
else
L = Mid + 1;
}
return R + 1;
}
int main() {
string S = "0??0";
cout << solve(S) << endl;
}입력
0??0
출력
2
정리
이 알고리즘은 각 위치에서 균형 값의 가능 범위를 구간 [L, R]로 관리하고, '?'마다 범위를 확장하면서 불균형 한도 x를 유지할 수 있는지 검사합니다. 여기에 이분 탐색을 결합하면 시간 복잡도 O(|S| log M)(M은 탐색 범위의 크기)으로 최소 불균형을 효율적으로 구할 수 있습니다.