Java 프로그래머스 소수 찾기

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

프로그래머스

문제 분류 : 코딩테스트 연습 > 완전탐색 > 소수 찾기

난이도 : 2

import java.util.*;
class Solution {
    static boolean [] memo;
    static boolean [] visited;
    static HashSet<Integer> set;
    static int size;
    static int n;
    static int answer;
    static String target;
    public int solution(String numbers) {
        answer = 0;
        // numbers는 길이 1 이상 7 이하인 문자열입니다.
        // 에라토스테네스의체
        memo = new boolean[9999999 + 1];
        for(int i = 2; i <= 9999999; i++){
            if(!memo[i]){
                int cnt = 2;
                while(i * cnt <= 9999999){
                    memo[i * cnt] = true;
                    cnt++;
                }
            }
        }
        memo[0] = true;
        memo[1] = true;
        size = numbers.length();
        target = numbers;
        set = new HashSet<>();
        visited = new boolean [size];
        for(int i = 1; i <= size; i++){
            n = i;
            BackTracking(0, "");    
        }
        return answer;
    }
    public static void BackTracking(int depth, String str){
        if(depth == n){
            int temp = Integer.parseInt(str);
            // System.out.println(temp);
            if(!set.contains(temp) && !memo[temp]){
                answer++;
                set.add(temp);
            }
            return;
        }
        for(int i = 0; i < target.length(); i++){
            if(!visited[i]){
                visited[i] = true;
                BackTracking(depth + 1, str + Character.toString(target.charAt(i)));
                visited[i] = false;
            }
        }  
    }
}