알고스팟 자바(java) 해답 : PI

import java.util.*;

public class Main {
	static int []cache;
	static int result;
	static int length;
	static String s;
	public static void main(String args[]) throws Exception {
	
        cache = new int[10000000];
    	int testcase;
    	int temp;
        Scanner scanner = new Scanner(System.in);
        testcase = scanner.nextInt();
        for(int i = 0; i < testcase; i++){	
        	Arrays.fill(cache,-1);
        	result = 987654321;
        	s = scanner.next();
        	length = s.length();
        	for(int k = 3; k <= 5; k++){
        		
        		int p = 0;
        		
        		temp = find(k,p);
        		
        		result =  Math.min(result, calculate(k,p) + temp); 
        		
     
        	}
        	
        	
        	System.out.println(result);
        	
        	
        }
    }
	
	static int find(int k, int p){
		
		int ret;
		
		int temp;
		
		
		if(p + k == length){
			return 0;
		}
		
		ret = cache[p+k];
		
		if(ret != -1)
			return ret;
		
		ret = 987654321;
		
		for(int i = 3; i <= 5; i++){
			
			if(p + k + i <= length){
				
				temp = find(i, p + k);
				
			
				ret = Math.min(ret, calculate(i, p + k) + temp);
				
				
			}
			
		}
		
		if(ret < 987654321){
			cache[p+k] = ret;
		}
		return ret;
	}
	
	
	static int calculate(int k, int p){
		int []t = new int[5];
		 
    	for(int i = 0; i < k; i++){
    		t[i] = Character.getNumericValue(s.charAt(p+i));
    	}
    	//first
    	boolean one = true;
    	int temp = t[0];
    	for(int i = 1; i < k; i++){
    		if(t[i] != temp){
    			one = false;
    			break;
    		}
    	}
    	if(one == true){
    		
    		return 1;
    	}
    	//second
    	boolean two = true;
    	temp = t[1] - t[0];
    	
    	if(temp == 1 || temp == -1){
    		for(int i = 2; i < k; i++){
    			
    			if(temp == 1){
    				if(t[i] - t[i-1] != 1){
    					two = false;
    					break;
    				}
    			}
    		
    			if(temp == -1){
    				if(t[i] - t[i-1] != -1){
    					
    					two = false;
    					break;
    				}
    			}
    		}
    	}
    	else
    		two = false;
    	
    	if(two == true){
    		
    		return 2;
    	}
    	//third
    	boolean three = true;
    	int temp1 = t[0];
    	int temp2 = t[1];
    	for(int i = 2; i < k; i++){
    		if(i % 2 == 0){
    			if(temp1 != t[i]){
    				three = false;
    				break;
    			}
    		}
    		else{
    			if(temp2 != t[i]){
    				three = false;
    				break;
    			}
    		}
    	}
    	if(three == true){
    		
    	    return 4;
    	}
    	//fourth
    	boolean four = true;
    	temp = t[1] - t[0];
    	for(int i = 2; i < k; i++){
    		if(t[i] - t[i-1] != temp){
    			four = false;
    			break;
    		}
    	}
    	if(four == true){
    		
    		return 5;
    	}
    	
    	return 10;
	}
}