[프로그래머스][JAVA] 소수 찾기 (완전 탐색, 소수)

220607

import java.util.*;
 
class Solution {
    public int solution(String numbers) {
        int answer = 0;
        Set<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(isPrime(a)){
                answer++;
            }
        }
        
        
        
        return answer;
    }
    private boolean isPrime(int n){
        if(n==2) return true;
        if(n==0 || n==1 || n%2==0){
            return false;
        }
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;   
    }
    
    private void permutation(String prefix, String str, Set set){
        int n = str.length();
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for(int i=0; i<n; i++){
            permutation(prefix+str.charAt(i), str.substring(0,i)
                +str.substring(i+1,n), set);
        }
        
    }
}

 

 

 

숫자 num의 소수 구하기는 (int)Math.sqrt(num)까지만 하면 된다

 

import java.util.*;
 
class Solution {
    private static boolean[] isVisited;
    private static Set<Integer> set;
    
    public int solution(String numbers) {
        int[] arr = Arrays.stream(numbers.split(""))                     
                        .mapToInt(Integer::parseInt).toArray();   
        isVisited = new boolean[arr.length];
        set = new HashSet<>();
        
        permutation(arr);
        int answer = 0;
        // set.forEach(System.out::println);
        for(Integer i : set){
            if(isPrimeNum(i)) answer++;
        }
         
        return answer;
    }
    
    private boolean isPrimeNum(int num){
        if(num==0 || num==1) return false;
        
        for(int i=2; i<=(int)Math.sqrt(num); i++){
            if(num%i==0) return false;
        }
        
        return true;
    }
    
    private void permutation(int[] arr){
        for(int i=1; i<=arr.length; i++){
            permutation(arr, new StringBuilder(), 0,i);
        }
    }
    
    private void permutation(int[] arr, StringBuilder sb, 
                                        int depth,int count){
        if(depth == count){
            // System.out.println(sb.toString());
            set.add(Integer.parseInt(sb.toString()));
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(!isVisited[i]){
                isVisited[i] = true;
                permutation(arr, sb.append(arr[i]), depth+1, count);
                sb.deleteCharAt(sb.length()-1);
                isVisited[i] = false;     
            }
        }
        
    }
    
    
// 에라토스테네스의 체를 미리 만들어놓은 다음에 풀려고 했는데 
// 택도 없음 n의 Math.sqrt(n)를 활용해서 구해야 시간에서 안터짐
//     private boolean[] getPrimeNumArr(int max){
//         boolean[] isPrimeNum = new boolean[max+1];
//         for(int i=2; i<=max; i+=2){
//             isPrimeNum[i]=true;
//         }
//         for(int i=2; i<=max; i++){
//             if(!isPrimeNum[i] && checkPrime(i)){
//                 for(int j=i; j<=max; j+=i){
//                     isPrimeNum[i]=true;
//                 }
//             }
//         }
        
//         return isPrimeNum;
//     }
    
//     private boolean checkPrime(int num){
//         for(int i=2; i<num; i++){
//             if(num%i==0) return true;
//         }
//         return false;
//     }
}