[프로그래머스][소수찾기]-Lv.2

✨ 문제

문제링크

✨ 제한사항

✨ 접근방법

1. String을 한개씩 쪼개어 char 배열로 만든다.
2. DFS를 통하여 모든 경우의 수를 구한다.
3. 경우의 수들을 소수인지 판단하여 Set에 집어 넣는다. (동일한 숫자가 나올 수 있기 때문에 Set을 이용했다)
4. DFS가 끝나면 Set의 크기를 반환한다.

✨ 코드

import java.util.*;
class Solution {
    static Set<Integer> set;
    static boolean[] visited;
    
    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        char[] arr = numbers.toCharArray();
        visited = new boolean[arr.length];
        dfs(0,arr,"");
        return set.size();
    }
    
    static void dfs(int depth, char[] arr, String str){
        if(!str.equals("")){
            int num = Integer.parseInt(str);
            if(isPrime(num)){
                set.add(num);
            }
        }
        if(depth == arr.length){
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(depth + 1, arr, str + arr[i]);
                visited[i] = false;
            }
        }
    }
    
    static boolean isPrime(int num){
        if(num<=1) return false;
        if(num==2) return true;
        for(int i=2; i<=Math.sqrt(num); i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }
}