[JAVA] 백준 3671 - 산업 스파이의 편지

https://www.acmicpc.net/problem/3671

주어진 최대 7개의 숫자로 만들수 있는 소수의 개수를 출력하는 문제이다.

만들수 있는 숫자의 최댓값이 9,999,999이므로 1천만 이하의 수에서 에라토스테네스의 채로 소수를 거르고,

DFS로 최댓값 이내로 모든 경우를 탐색 후 중복 없는 소수의 개수를 출력했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static boolean[] era = new boolean[10000000];
    static int count = 0;
    static HashSet<String> set = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = par(br.readLine());

        era[0] = true;
        era[1] = true;
        for (int i = 2; i <era.length ; i++) {
            if(era[i]) continue;
            for (int j = i+i; j < era.length ; j+=i) {
                era[j] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            count = 0;
            set.clear();
            String s = br.readLine();
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            char[] cr = reverse(ca);
            int max = Integer.parseInt(String.valueOf(cr));
            for (int j = 0; j < ca.length ; j++) {
                char c = ca[j];
                if(c=='0') continue;
                boolean[] visited = new boolean[ca.length];
                visited[j] = true;
                dfs(String.valueOf(c),ca,max,visited);
            }
            System.out.println(count);
        }
    }
    static void dfs(String s, char[] ca, int max,boolean[] visited){
        if(par(s)>max) return;
        if(set.contains(s)) return;
        set.add(s);
        if(!era[par(s)]) count++;
        for (int i = 0; i < ca.length ; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            dfs(s.concat(String.valueOf(ca[i])),ca,max,visited);
            visited[i] = false;
        }
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    static char[] reverse(char[] arr){
        char[] arr2 = new char[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[arr.length-1-i];
        }
        return arr2;
    }
    static int[] reverse(int[] arr){
        int[] arr2 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[arr.length-1-i];
        }
        return arr2;
    }
}