package T0405;

import java.util.*;

public class t3 {
	
    public static int solution(String road, int n) {
        int answer = 0;
        
        StringBuilder sb = new StringBuilder();
        sb.append(road);
        
        int ck = 0;
        for(int i=0;i<road.length(); i++) {
        	if(road.charAt(i) == '0')
        		ck++;
        }
        
        if(ck <=n)
        	return road.length();
        
        int lock = 0;
        LinkedList<Integer> zero_idx_list = new LinkedList<>();
        
        for(int i=0; i<road.length(); i++) {
        	char zero_chk = road.charAt(i);
        	
        	if(zero_chk == '0') {
	        	if(lock <n) {
	        		sb.replace(i, i+1, "1");
	        		zero_idx_list.add(i);
	        		lock++;//와 씨 락을 걸어줬으면서 어떻게 lock을 ++을 안해줘....
	        	}
	        	
	        	else {//lock을 옮겨준다
	        		int zero_first_idx = zero_idx_list.removeFirst();
	        		sb.replace(zero_first_idx, zero_first_idx+1, "0");
	        		sb.replace(i, i+1, "1");
	        		zero_idx_list.add(i);
	        	}
        	}//if
        	
        	//다 옮겨주고 나와서 연속 1의 개수 확인
        	String sr = sb.toString();
        	String res[] = sr.split("0");
        	
        	for(int j=0; j<res.length; j++) {
        		answer = Math.max(answer, res[j].length());
        	}
        	
        }//for
        
        
        return answer;
    }
	
	public static void main(String[] args) {
		String s = "111011110011111011111100011111";
//		String s = "001100";
		
		System.out.println(solution(s,3));
	}
}

package T0405;

//30min
public class t2 {

    public int solution(String answer_sheet, String[] sheets) {
        int answer = 0;
        char as[] = new char[answer_sheet.length()];
        
        int max = 0;
        
        for(int i=0; i<answer_sheet.length(); i++)
        	as[i] = answer_sheet.charAt(i);
        
        for(int i=0; i<sheets.length; i++) {
        	for(int j=i+1; j<sheets.length; j++) {
        		
        		int serise = 0;
        		int s = 0;
        		int plus = 0;
        		
        		for(int k=0; k<answer_sheet.length(); k++) {//여기서 비교
        			if(sheets[i].charAt(k) == sheets[j].charAt(k)) {
        				if(sheets[i].charAt(k) != as[k]) {
        					plus++;
        					serise++;
        					
            				if(s==0 && k == answer_sheet.length()-1)
        						s = 1;
        				}
        			}
        			
        			else {
        				s = Math.max(s, serise);
        				serise = 0;    					
        			}
        		}
        		
        		max = Math.max(max, plus + (s*s));
        	}
        }
        
        answer = max;
        
        return answer;
    }
	
	public static void main(String[] args) {
		
	}
}

package T0405;

import java.util.*;


//20min
public class t1 {
    public static int solution(String inputString) {
        int answer = -1;
        
        int an = 0;
        boolean chk = false;
        LinkedList<Character> stk = new LinkedList<>();
        
        for(int i=0;i<inputString.length(); i++) {
        	char c = inputString.charAt(i);
        	
        	if(c == ')' || c == '}' || c == ']' || c=='>') {
        		chk = true;
        		
        		if(!stk.isEmpty() && c == ')' && stk.contains('(')) {
        			int idx = stk.indexOf('(');
        			stk.remove(idx);
        			
        			an++;
        		}
        		
        		if(!stk.isEmpty() && c=='}' && stk.contains('{')) {
        			int idx = stk.indexOf('{');
        			stk.remove(idx);

        			an++;
        		}
        		if(!stk.isEmpty()&& c==']' && stk.contains('[')) {
        			int idx = stk.indexOf('[');
        			stk.remove(idx);
        			an++;
        		}
        		if(!stk.isEmpty() && c=='>' && stk.contains('<')) {
        			int idx = stk.indexOf('<');
        			stk.remove(idx);
        			
        			an++;
        		}
        		
        		//헉... 이거 안해줘서 틀림..ㅎ
        		else
        			stk.push(c);
        	}
        	
        	else if(c == '(' || c == '{' || c == '[' || c=='<') {
        		stk.push(c);
        		chk = true;
        	}
        		
        }
        
        if(chk == false)
        	return 0;
        
        if(stk.isEmpty())
        	answer = an;
        
        return answer;
    }
    
    public static void main(String[] args) {
		
    	String input = "([)]]";
    	
    	System.out.println(solution(input));
	}
}

//반례 -> ({)}}
				else
        			stk.push(c);

package Dynamic_programming;

import java.util.*;

public class line_나잡아봐라 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int co = sc.nextInt();
		int br = sc.nextInt();
		
		int pos[] = new int[200001]; //값을 min 초 취급
		int answer = -1;
		
		Queue<Integer> qu = new LinkedList<>();
		
		qu.add(br);
		
		while(true) {
			int num = qu.poll();
			
			int time = pos[num];
			int cony = 0;
			for(int i=1; i<=time; i++)
				cony += i;
			
			if(num == co + cony) {
				answer = pos[num];
				break;
			}
			
			int next=0;
			for(int i=0; i<3; i++) {
				if(i==0)
					next = num-1;
				if(i==1)
					next = num+1;
				if(i==2)
					next = num*2;
				
				if(next>=0 && next<200001 && pos[next] ==0) {
					qu.add(next);
					pos[next] = pos[num]+1;
				}
			}
		}
		
		System.out.println("answer " + answer);
	}
}

package Dfs_Bfs;

import java.util.*;

public class beak_re_여행경로 {

	static LinkedList<String> result = new LinkedList<>();
	
	static public void dfs(String tic[][], boolean ck[], String s, String input, int count) {
		s += "," + input;
		
		if(count == tic.length) {
			//끝까지 다 돌았으면
			result.add(s);
		}

		for(int i=0; i<tic.length; i++) {
    		if(tic[i][0].equals(input) && !ck[i]) {
    			ck[i] = true;	
    			dfs(tic, ck, s, tic[i][1], count+1); //초기화 String, size
    			ck[i] = false;
    		}
		}//for
		
	}
	
    static public String[] solution(String[][] tickets) {
    	for(int i=0; i<tickets.length; i++) {
    		
    		if(tickets[i][0].equals("ICN")) {
    			boolean chk[] = new boolean[tickets.length];
    			chk[i] = true;
    			dfs(tickets, chk, "ICN",  tickets[i][1], 1); //초기화 String, size
    			chk[i] = false;
    		}
    		
    	}
    	
    	result.sort(null);
    	
    	return result.get(0).split(",");
    }
}