[Educational Codeforces Round 149 (Rated for Div. 2)] C. Best Binary String

 

 

---

https://codeforces.com/blog/entry/116752

Educational Codeforces Round 149 Editorial - Codeforces

 

011110010

0[1110010] -> 00[100]111 -> 00001111

 

※ 문자열에 [10]을 최대한 없애야한다.

(110, 010)

 

※. [10] 이 있다면 같은수끼리 뭉치게 만든다.

(111000, 100000, 111110, 반전했을때 가장 적은수로 오름차순)

 

※. 문자열에 ? 가 있는곳은 전의 문자를 붙인다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
 
public class Main {
 
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			char[] arr = br.readLine().toCharArray();
			char x = '0';
			for(int i = 0; i < arr.length; i++) {
				if(arr[i] == '?') arr[i] = x;
				x = arr[i];
			}
			for(int i = 0; i < arr.length; i++) sb.append(arr[i]);
			sb.append('\n');
		}
		System.out.println(sb);
	}
}