[프로그래머스] 완전탐색. 소수 찾기

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

문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

소수를 찾는 문제입니다만, 소수 보다는 순열을 이용하는 부분이 더 어렵게 느껴졌습니다.

조합과 순열의 차이는 순서가 있느냐 없느냐 인데요. 

 

순열의 경우 

1, 2

2, 1
은 서로 다르지만 조합은 같은 것으로 생각하는 것입니다. 순서가 없으니 1,2 과 2,1은 중복 되는 것이죠.

 

우리가 해결 해야 하는 문제는 모든 경우의 수를 봐야 하기 때문에 조합이 아닌 순열로 접근해야 합니다.

순열과 소수를 구하는 소스코드는 구글링을 통하여 작성하게 되었습니다.

 

아래는 소스코드 입니다.

 

import java.util.*;

public class FindPrimeNumber {
    private static final Set<Integer> PRIME = new HashSet<>();

    public static int solution(String numbers) {
        String[] numberArr = numbers.split("");

        for (int r = 1; r <= numberArr.length; r++) {
            permutation(numberArr, 0, numberArr.length, r);
        }

        return PRIME.size();
    }

    private static void permutation(String[] arr, int depth, int n, int r) {
        if (depth == r) {
            int number = parseInt(arr, r);

            if (isPrime(number)) {
                PRIME.add(number);
            }
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }

    private static int parseInt(String[] arr, int r) {
        StringBuilder s = new StringBuilder();

        for (int i = 0; i < r; i++) {
            s.append(arr[i]);
        }

        return Integer.parseInt(s.toString());
    }

    private static void swap(String[] numberArr, int depth, int i) {
        String temp = numberArr[depth];
        numberArr[depth] = numberArr[i];
        numberArr[i] = temp;
    }

    private static boolean isPrime(int number) {
        if (number == 0 || number == 1) {
            return false;
        }

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