[JAVA]소수 찾기(Promgrammers)

문제

문제

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

풀이

 문제를 보고 이 문제는 순열 문제라고 생각하였다. 입력된 수들을 이용해 여러 수들을 만들어 소수인지 아닌지 판별하여 새로운 배열을 만들면 된다라는 생각이 들었다.
 조합과 순열의 알고리즘 핵심이다. 내용은 아래와 같다.

조합 ($_n\mathrm{C}_r$)

public class Combination {

    public static void main(String[] args) {
        Combination ex = new Combination();
        int[] arr = {1, 3, 5, 7, 9};
        int n = arr.length;
        int r = 3;
        // 크기가 5인 수열 arr에서 r인 3r개를 뽑은 경우를 출력한다. 
        int[] combArr = new int[n]; // 뽑은 원소의 인덱스를 저장하는 배열 

        ex.doCombination(combArr, n, r, 0, 0, arr);

    }

    public void doCombination(int[] combArr, int n, int r, int index, int target, int[] arr) {
        if(r == 0) {
            // 다 뽑았을 때 
            for(int i=0; i<index; i++)
                System.out.print(arr[combArr[i]] + " ");
            System.out.println();
        } else if (target == n) 
            return;
            //r개를 다 못뽑았는데 arr의 모든 원소를 다 검사했을 때, 실패 -> 아무것도 안하고 끝난다. 
        else {
            combArr[index] = target;
            doCombination(combArr, n, r-1, index+1, target+1, arr); // (i) 원소를 뽑는 경우 
            doCombination(combArr, n, r, index, target+1, arr); // (ii) 원소를 안뽑는 경우 
        }
    }

}

 recursion으로 이루어진다. 대략 알고리즘을 보자면 dfs를 이용해 0-1 knapsack 알고리즘처럼 arr에 포함된 item들이 하나의 레벨에 해당되는 트리구조이다. 현재 level에 원소가 포함되냐 포함되지 않냐를 매개변수 차이를 주어 recursion 자식 노드들을 생성하며 진행된다. 다 뽑았을 때 코드를 바꾸어 리스트나 배열에 할당해줄수 있다.

순열 ($_n\mathrm{P}_n$)

$_n\mathrm{P}_r$을 구현하기 전에 먼저 $_n\mathrm{P}_n$을 구현해보자.

public class Permutation {

    public static void main(String[] args) {
        Permutation ex = new Permutation();
        int[] arr = {1, 2, 3, 4};
        // arr 배열 자체를 메소드에서 정렬한다.
        ex.doPermutation(arr, 0);
    }

    public void doPermutation(int[] arr, int startIdx) {
        int length = arr.length;
        if(startIdx == length - 1) {
            for(int n: arr)
                System.out.print(n + " ");
            System.out.println();
            return;
        }
        for(int i = startIdx; i < length; i++) {
            swap(arr, startIdx, i);
            doPermutation(arr, startIdx + 1);
            swap(arr, startIdx, i);
        }
    }
    public void swap(int[] arr, int n1, int n2) {
        int temp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = temp;
    }
}

 배열에서 순서를 바꿔가며 recursion을 수행한다. startIdx가 n에 도달한다면 출력을 한다.

순열 ($_n\mathrm{P}_r$)

 $_n\mathrm{P}_r$은 $_n\mathrm{P}_n$과 $_n\mathrm{C}_r$을 합친 코드이다. $_n\mathrm{C}_r$을 통해 n개 중에 r개를 뽑은 후, 수열을 구성해주면 된다.

public class Permutation2 {
    public static void main(String[] args) {
        Permutation2 ex = new Permutation2();
        int[] arr = {1, 3, 5, 7, 9};
        int n = arr.length;
        int r = 3;
        int[] combArr = new int[r];
        ex.doCombination(combArr, arr, n, r, 0, 0);
    }
    public void doCombination(int[] combArr, int[] arr, int n, int r, int index, int target) {
        if(r == 0) {
            doPermutation(combArr, 0);
        } else if(target == n)
            return;
        else {
            combArr[index] = arr[target];
            doCombination(combArr, arr, n, r-1, index+1, target+1);
            doCombination(combArr, arr, n, r, index, target+1);
        }
    }
    public void doPermutation(int[] arr, int startIdx) {
        int length = arr.length;
        if(startIdx == length - 1) {
            for(int item: arr)
                System.out.print(item + " ");
            System.out.println();
            return;
        }
        for(int i = startIdx; i < length; i++) {
            swap(arr, startIdx, i);
            doPermutation(arr, startIdx + 1);
            swap(arr, startIdx, i);
        }
    }
    public void swap(int[] arr, int n1, int n2) {
        int temp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = temp;
    }
}

 최종적으로 본 문제는 $_n\mathrm{P}_r$을 이용해 수들을 구성하고, 소수인지 판별하면 된다. 동혁이와 정연이는 소수 문제라서 에라토스테네스의 체를 사용하여 풀었지만 나는 특정 수를 매개변수로 하여 2부터 특정 수/2까지 반복문을 돌며 나누어 떨어지는 수가 있다면 false를 리턴하는 함수를 만들어 풀었다. true라면 세트에 추가하여 최종적으로는 개수를 출력한다. 에라토스테네스의 체를 애초에 못 떠올린것도 문제다. 문제를 아직 부족하게 풀었나보다. 공부를 열심히 해야겠다는 다짐을 했다.

    public static int solution(String numbers) throws Exception{
        //입력 및 할당
        String str = br.readLine();
        int[] arr = new int[str.length()];
        for(int i = 0; i < str.length(); i++)
            arr[i] = str.charAt(i) - '0';
        //반복문을 통해 순열 및 조합
        int n = arr.length;
        for(int r = 1; r <= n; r++){
            int[] comb_arr = new int[r];
            doCombination(comb_arr, arr, n, r, 0, 0);
        }
        System.out.println(set.size());
        return 0;
    }
    //순열 및 조합 함수
    public static void doCombination(int[] comb_arr, int[] arr, int n, int r, int idx, int target){
        if(r == 0)
            doPermutation(comb_arr, 0);
        else if(target == n){
            return;
        }
        else{
            comb_arr[idx] = arr[target];
            doCombination(comb_arr, arr, n, r-1, idx+1, target+1);
            doCombination(comb_arr, arr, n, r, idx, target+1);
        }
    }
    //순열 함수
    public static void doPermutation(int[] arr, int start_idx){
        int length = arr.length;
        if(start_idx == length - 1){
            int num = 0;
            //배열에서 수를 꺼내 새로운 수를 구성
            for(int item : arr){
                num *= 10;
                num += item;
            }
            //소수라면 세트에 추가
            if(check(num))
                set.add(num);
            return;
        }
        for(int i = start_idx; i < length; i++){
            swap(arr, start_idx, i);
            doPermutation(arr, start_idx + 1);
            swap(arr, start_idx, i);
        }
    }
    //배열에서 값의 순서를 바꾸는 함수
    public static void swap(int[] arr, int n1, int n2){
        int tmp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = tmp;
    }
    //소수인지 판별하는 함수
    public static boolean check(int number){
        if(number == 1 || number == 0)
            return false;
        for(int i = 2; i < number/2; i++){
            if(number % i == 0)
                return false;
        }
        return true;
    }