Lv 2. 소수찾기

 

코드 흐름

• DFS로 순열을 만들어 하나하나 의 가짓수를 만드는 DFS 함수
• 하나하나의 가짓수가 나올때마다 소수인지 체크하는 check 함수를 만들어 풀이하였다.
• 소수판별은 가장 효과적인 n의 제곱근까지 반복문을 돌려 확인하였고
• 시간복잡도를 위해 가짓수의 중복판별은 Set 을 이용하였다.

import java.util.*;
class Solution {
    Set<Integer> isVisited;
    int answer;
    boolean[] numbersVisited;
    public void DFS(int n, int s, String numbers){
        if(n>=0 && !isVisited.contains(s)){
            if(check(s))
                answer++;
            isVisited.add(s);
        }
        for(int i = 0 ; i < numbers.length() ; i++)
            if(!numbersVisited[i])
            {
                numbersVisited[i]=true;
                DFS(n-1,(s*10)+numbers.charAt(i)-'0',numbers);
                numbersVisited[i]=false;
            }
    }
    public int solution(String numbers) {
        answer = 0;
        isVisited = new HashSet<>();
        numbersVisited = new boolean[numbers.length()];
        DFS(numbers.length(), 0 ,numbers);
        return answer;
    }
    public boolean check(int num){
        if (num < 2) {
            return false;
        }
        for(int i = 2 ; i <= Math.sqrt(num) ; i++){
            if(num%i==0)
                return false;
        }
        return true;
    }
}