[프로그래머스] 소수 찾기 (dfs)

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

import java.util.*;

class Solution {
    public boolean[] visited = new boolean[7];
    public Set<Integer> set;
    
    public int solution(String numbers) {
        int answer = 0;
        
        set = new HashSet<>(); //중복을 피해야하기 때문
        dfs(numbers, "",0);
        
        for(int num: set){
            if(isPrime(num)){
                answer +=1;        
            }
        }
        
        return answer;
        
    }
    
    public void dfs(String numbers, String str, int len){
        
     if(len > numbers.length()){
            return;
        }
        
        for(int i = 0; i< numbers.length(); i++){
            if(!visited[i]){ //방문한 적이 없으면
                visited[i] = true;
                set.add(Integer.parseInt(str + numbers.charAt(i))); //추가를 하고
                dfs(numbers, str + numbers.charAt(i), len + 1); // 길이 올려주기
                visited[i] = false; //다음꺼 해줘야하니까 백트래킹
            }
        }
    }
    
    public boolean isPrime(int num){
        if(num < 2){
            return false;
        }
        for(int i = 2; i<num; i++){
            if(num % i == 0){
                return false;
            }
        }
        
        // 에라토스테네스 체
        // for (int i = 2; i <= (int) Math.sqrt(n); i++) {
        //     if (n % i == 0) {
        //         return false;
        //     }
        // }
        
        return true;
    }
}