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

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

class Solution {
    static ArrayList<Integer> allDecimal = new ArrayList<>();
    static String temp = "";
    static Set<String> perArr = new HashSet<>();

    public int solution(String numbers) {
        int answer = 0;
        String[] numberArr = numbers.split("");
		// 만들 수 있는 제일 큰 숫자
        Arrays.sort(numberArr);
        for (String str : numberArr) temp = str + temp;
		// 범위 내의 모든 소수 추출
        decimal(Integer.parseInt(temp));
        for (int i = 1; i < numberArr.length + 1; i++)
            perm(numberArr, 0, numberArr.length, i);
        for (String s : perArr) {
            for (Integer integer : allDecimal) {
                if (s.equals(integer.toString())) {
                    answer++;
                    break;
                }
            }
        }

        return answer;
    }

    private static void decimal(int max) {
        boolean[] arr = new boolean[max + 1];    //true 이면 해당 인덱스 소수.
        arr[0] = arr[1] = false;
        for (int i = 2; i <= max; i += 1) {
            arr[i] = true;
        }
        //2 부터 숫자를 키워가며 배수들을 제외(false 할당)
        for (int i = 2; i * i <= max; i += 1) {
            for (int j = i * i; j <= max; j += i) {
                arr[j] = false;        //2를 제외한 2의 배수 false
            }
        }
        for (int i = 0; i <= max; i += 1) {
            if (arr[i]) {
                allDecimal.add(i);
            }
        }
    }

    public static void perm(String[] arr, int depth, int n, int k) {
        if (depth == k) {
            save(arr, k);
            return;
        }
        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth);
        }
    }

    // 자바에서는 포인터가없기 때문에아래와 같이, 인덱스i와 j를통해 바꿔줌.
    public static void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void save(String[] arr, int k) {
        String number = "";
        for (int i = 0; i < k; i++) number += arr[i];
        perArr.add(number);
    }
}