프로그래머스 lv2 소수 찾기

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

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

제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbers return
"17" 3
"011" 2
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

 

문자열을 조합하고 해당 숫자가 소수인지 판별하는 메소드에 돌립니다.

 

숫자의 조합은 중복이 없어야 하기 때문에 HashSet에 저장하고,

반복문 내에서 재귀적으로 문자열을 조합합니다.

 

여기서 소수인지 탐색하는 범위를 줄이고 효율성을 높이려면

N이 17일 때 2부터 16까지 탐색해서 소수인지 찾는 것보다

2부터 4까지만 구하면 됩니다.

17이 특정 수의 곱셈이라면 제곱근 앞뒤로 대칭이 이루어지기 때문에,

예를 들어 12는 2*6이자 6*2이기 때문에, 12의 제곱근인 3.4까지만 찾아도 소수인지 알아낼 수 있습니다.

 

public static HashSet<Integer> numberSet = new HashSet<>();

public static int solution(String number) {
        int result = 0;

        getNumber("", number);

        for (Integer n : numberSet) {
            if (isNum((int) n))
                result++;
        }

        return result;
    }

    public static void getNumber(String comb, String others) {
        if (!comb.equals("")) {
            numberSet.add(Integer.valueOf(comb));
        }

        for (int i = 0; i < others.length(); i++) {
            getNumber(comb + others.charAt(i),
                    others.substring(0, i) + others.substring(i + 1));
        }
    }

    public static boolean isNum(int num) {
        //1이거나 2의 배수이면 
        if (num <= 1)
            return false;
        int sqrt = (int) Math.round(Math.sqrt(num));
        for (int i = 2; i <= sqrt; i++) {
            //특정 숫자로 나눠지면 소수가 아니므로 false 반환
            if (num % i == 0)
                return false;
        }
        return true;
    }