[완전탐색] 소수 찾기 (JAVA)

# 문제 설명

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

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

---

제한사항

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

---

입출력 예

numbers return

"17"	3
"011"	2

 

# 정답 코드

    public static ArrayList<Integer> number = new ArrayList<>(); //만들 수 있는 숫자 리스트

    /* Main 함수 */
    public static int solution(String numbers) {
        int answer = 0;

        String[] oneNum = new String[numbers.length()]; //주어진 숫자를 한 글자씩 저장

        for (int i = 0; i < oneNum.length; i++) {
            oneNum[i] = String.valueOf(numbers.charAt(i));
        }

        String[] output = new String[oneNum.length];
        boolean[] visited = new boolean[oneNum.length];

        for (int i = 0; i < oneNum.length; i++) {
            permutation(oneNum, output, visited, 0, i + 1);
        }

        for (int n : number) {
            if (isPrime(n)) {
                answer++;
            }
        }

        return answer;
    }

    /* 순열 함수 (원본배열, 출력배열, 방문여부 체크, 현재 탐색하고 있는 인덱스, 뽑고자 하는 개수) */
    public static void permutation(String[] input, String[] output, boolean[] visited, int depth, int r) {
        if (depth == r) {
            String num = output[0];

            for (int i = 1; i < r; i++) {
                num = num + output[i];
            }

            if (!number.contains(Integer.parseInt(num))) {
                number.add(Integer.parseInt(num));
            }

            return;
        }

        for (int i = 0; i < input.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = input[i];
                permutation(input, output, visited, depth+1, r);
                visited[i]=false;
            }
        }
    }

    /* 소수인지 판별하는 함수 */
    public static boolean isPrime(Integer num) {
        //0과 1은 소수가 아님
        if (num <= 1) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

 

입력 받은 numbers를 한 글자씩 분리하여 배열에 따로 저장한다.

 

숫자 카드로 만들 수 있는 수를 구하기 위해 순열을 사용했다.

순열 함수의 for문을 돌면서, output 배열에 카드로 만들 수 있는 숫자가 저장된다.

만약 depth와 r이 같으면, output 배열에 있는 숫자를 합쳐 number(만들 수 있는 숫자 리스트)에 추가한다.

 

number를 모두 채우고 난 후, 그 숫자들이 소수인지 판별한다.

소수인지 판별하는 함수인 isPrime() 함수를 이용한다.

소수는 1과 자기 자신으로만 나누어 떨어지는 수를 의미한다.

0과 1은 소수가 아니므로 false를 리턴한다.

자기 자신 이외의 숫자로 나누어 떨어지면 소수가 아니므로 false를 리턴한다.

 

이때 Math.sqrt() 함수를 이용한다. (제곱근)

num = 8인 경우에서,
1 x 8 = 8

2 x 4 = 8

4 x 2 = 8

8 x 1 = 8

위 곱셈식이 가능하다.

Math.sqrt(num) = 2√2 이다.

곱셈식들은 2√2를 기준으로 대칭적으로 존재한다.

따라서 for문을 Math.sqrt(num)까지로 제한하여도 소수를 판별할 수 있고, 반복 횟수도 줄일 수 있다.

 

isPrime() 함수를 이용하여 소수를 answer에 카운트하고 리턴한다.