[백트래킹] 산업 스파이의 편지(백준 3671번, 자바)☆☆☆

3671번: 산업 스파이의 편지 (acmicpc.net)

3671번: 산업 스파이의 편지

 

 

 

백트래킹

import java.util.*;
import java.io.*;


public class Main3 {

	static boolean[] visit;
	static int N;
	static ArrayList<Integer> arr;
	static String s;	
	static char[] c;
	
	public static void main(String[] args) throws IOException {
		
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int C=Integer.parseInt(br.readLine());
	
		

		for(int t_c=1;t_c<=C;t_c++) {
			
			s=br.readLine();
			c=s.toCharArray();
			arr=new ArrayList<>();
			
			visit=new boolean[s.length()];
			StringBuilder sb=new StringBuilder("");
			
			for(int i=0;i<s.length();i++) {
				sb.append(c[i]);
				createString(i,sb);
				sb=new StringBuilder("");
				visit[i]=false;
				
			}
		int answer=0;
		for(Integer num: arr) {
				if(isPrime(num)) answer++;
		}
			
		System.out.println(answer);
		}
		
	
	}
	

	
	static void createString(int x,StringBuilder str) {
		
		if(str.length()>s.length()) return;
		visit[x]=true;
		int num=Integer.parseInt(str.toString());
		if(!arr.contains(num))
			arr.add(num);
		
		for(int i=0;i<s.length();i++) {
			if(!visit[i]) {
				createString(i, str.append(c[i]));
				visit[i]=false;
				str.delete(str.length()-1,str.length());
				
			}
		}
	}
	//소수 구하기 
			static boolean isPrime(int num) {
					if(num<=1) return false;
				   for(int i=2; i<=Math.sqrt(num); i++){
			            if(num%i == 0) return false;
				   }
			        return true;
			}
	
}