[level2] 프로그래머스 - 소수 찾기(JAVA)

- 문자를 1~N(문자열길이)개 선택하여 줄세우는 경우의 수를 구한다.   => 순열

 

 

- N개의 문자를 줄세웠다면, 소수인지 확인 후 Set에 넣어준다.    => 에라토스테네스의 체
   Set은 중복을 허용하지 않기 때문에, 같은 숫자가 들어와도 상관 없다.

 

 

- Set에 들어있는 숫자의 개수를 리턴한다.

 

 

import java.util.*;

class Solution {
    static boolean isUsed[];
    static Set<Integer> prime;
    
    public int solution(String numbers) {
        prime = new HashSet<Integer>();
        isUsed = new boolean[numbers.length()];
        for(int i = 1; i <= numbers.length(); i++)
            comb(i, "", numbers);
        
        return prime.size();
    }
    
    static void comb(int N, String num, String numbers) {
        if(num.length() == N) {
            int n = Integer.parseInt(num);
            if(n > 1 && isPrime(n))
                prime.add(n);
        }
        
        for(int i = 0; i < numbers.length(); i++) {
            if(!isUsed[i]) {
                isUsed[i] = true;
                comb(N, num + numbers.charAt(i), numbers);
                isUsed[i] = false;
            }
        }
    }
    
    static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0)
                return false;
        }
        return true;
    }
}