C. Binary String - Educational Codeforces Round 128 (Rated for Div. 2)

Binary Search를 사용하는 문제입니다.
삭제된 1의 개수와 남아있는 0의 개수 중 큰 값의 최소값을 찾아야됩니다.

삭제하는 1의 개수를 binary search로 찾아야됩니다.
1을 삭제하면, 뒤에 있는 0들도 같이 지우는 것이 이득입니다. 그래서 1을 하나 지울 때 지워지는 0의 개수들을 저장해둡니다. 앞과 뒤 양방향에서 지울 수 있으므로 배열 2개를 이용해서 지워지는 0의 개수들을 저장해둡니다.

이제 binary search로 삭제하는 1의 개수를 찾습니다. 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Integer t = Integer.parseInt(sc.nextLine());
        while (t-- > 0) {
            List<Integer> input = Arrays.stream(sc.nextLine().split("")).map(str -> Integer.parseInt(str))
                    .collect(Collectors.toList());
            int n = input.size();
            long numOnes = input.stream().reduce((x, y) -> x + y).get();
            long numZeros = n - numOnes;
            // save the number of removed zeros when remove i number of one from begin
            List<Long> removedZerosFromFirst = new ArrayList<>();
            // save the number of removed zeros when remove i number of one from end
            List<Long> removedZerosFromLast = new ArrayList<>();
            long cnt = 0;
            for (int i = 0; i < n; i++) {
                if (input.get(i) == 0) {
                    cnt++;
                } else {
                    removedZerosFromFirst.add(cnt);
                }
            }
            removedZerosFromFirst.add(cnt);
            cnt = 0;
            for (int i = n - 1; i >= 0; i--) {
                if (input.get(i) == 0) {
                    cnt++;
                } else {
                    removedZerosFromLast.add(cnt);
                }
            }
            removedZerosFromLast.add(cnt);
            long l = 0;
            long r = numOnes;
            long ans = 0;
            while (l <= r) {
                long mid = (l + r) / 2;
                boolean isPossible = false;
                for (int i = 0; i <= mid; i++) {
                    long leftZeros = numZeros;
                    leftZeros -= removedZerosFromFirst.get(i);
                    leftZeros -= removedZerosFromLast.get((int) mid - i);
                    if (leftZeros <= mid) {
                        isPossible = true;
                        break;
                    }
                }
                if (isPossible) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            System.out.println(ans);
        }
        sc.close();
    }
}