소수 찾기(완전 탐색) **

사용 알고리즘: 순열

사용 언어: java

 

import java.util.*;

class Solution {
    static HashSet<Integer> set = new HashSet<>();
    static boolean[] visited ;
    static char[] numbers_char;
    
    public int solution(String numbers) {
        numbers_char = new char[numbers.length()];
        visited = new boolean[numbers.length()];
        for(int i=0; i<numbers.length(); i++){
            numbers_char[i] = numbers.charAt(i);
        }
        
        permutation("", 0);
        
        System.out.println(set);
        return set.size();
    }
    
    private static void permutation(String str, int idx){
        if(str != "") {
            if( isPrime(Integer.parseInt(str)) ) 
                set.add(Integer.parseInt(str));
        }
        
        if(idx == numbers_char.length) return;
        
        for(int i=0; i<numbers_char.length; i++) {
            if( !visited[i] ) {
                visited[i] = true;
                permutation( str+numbers_char[i], idx+1 );
                visited[i] = false;
            }
        }
    }
    
    private static boolean isPrime(int num) {
        if(num==0 || num==1) return false;
        for(int i=2; i<=Math.sqrt(num); i++) {
            if(num%i == 0) return false;
        }
        return true;
    }
}

 

 

알고리즘 선택 이유:

중복 제거를 위해 : set 사용

뽑는 순서가 상관 있으니까 permutation 사용