import java.util.*;
class Solution {
static char[] crr;
static boolean[] ch;
static int cnt=0;
static ArrayList<Integer> arr = new ArrayList<>();
public static boolean isPrime(int sum){
if(sum==0 || sum==1) return false;
else{
for(int i=2; i<sum; i++){
if(sum%i==0) return false;
}
}
return true;
}
public static void DFS(String sum,int length){
if(sum.length()==length){
int num = Integer.parseInt(sum);
if(isPrime(num)==true && !arr.contains(num)){
arr.add(num);
}
}
else{
for(int i=0; i<crr.length; i++){
if(!ch[i]){
ch[i]=true;
DFS(sum+=crr[i],length);
ch[i]=false;
sum = sum.substring(0,sum.length()-1); //초기화
}
}
}
}
public int solution(String numbers) {
int answer = 0;
//DFS돌려서 각각의 조합마다 -> isPrime()으로 소수 판별
crr = numbers.toCharArray();
ch = new boolean[crr.length];
for(int i=0; i<crr.length; i++){
DFS("",i+1);
}
return arr.size();
}
}
DFS()의 대표적인 문제라고 할 수 있다. 이 문제를 해결하는 데 애를 먹었다.
꼭 다시 봐야할 문제라고 생각한다. 아무튼 해결!