Today's Algorithm(2019-01-10)

programmers. 소수 찾기

언젠가, 그리고 조만간 '조합'을 이용한 알고리즘 문제를 풀 날이 올 거라 생각을 했습니다. 그리고 오늘이 그런 날인 것 같더라구요. 수들이 주어졌을 때 이 수로 만들 수 있는 수의 조합들 중에서 소수가 나오는 개수를 구하는 문제입니다.

 

별 생각이 안 들었습니다. 만들 수 있는 수들의 조합을 구하고(자리수가 다른 수가 만들어질 수 있기 때문) 각각의 조합에 대해 순열로 구성해서 그 수가 소수인지 찾도록 하였습니다. 그게 다였습니다. 조합은 인터넷에 있는 일반적인 조합을 가져다 썼고, 순열은 지난번에 만들어둔 순열 코드를 사용하였고, 소수는 가장 보편적인 방법 인 자기 수까지 수를 나누면서 1과 자신이외에 나누어지는 수가 있으면 소수가 아닌 것으로 판별하도록 하였습니다.

 

문제를 풀면서도 찝찝한 것은 지난번에 순열을 짜둔 코드가 어떤 식으로 동작하는지 명확히 생각이 안나고, 조합 또한 어떻게 동작하는지 전혀 모르고 있다는 점입니다... 결국 짜집기로 문제를 푼거나 다름없죠. 다른 문제를 풀기전에 꼭 짚고 넘어가야할 것 같습니다.

class Solution {
    Set<Integer> numSet = new HashSet<>();

    public int solution(String numbers) {
        String[] numText = numbers.split("");
        int[] num = new int[numText.length];
        for (int i = 0; i < numText.length; i++) {
            num[i] = Integer.valueOf(numText[i]);
        }

        for (int i = 1; i <= num.length; i++) {
            int[] data = new int[i];
            combinationUtil(num, data, 0, num.length - 1, 0, i);  // 해당 자리수만큼 조합을 구함
        }

        return numSet.size();
    }

    void combinationUtil(int arr[], int data[], int start,
                         int end, int index, int r)
    {
        if (index == r)
        {
            permutation(data, 0, data.length, data.length);  // 해당 자리수의 조합이 만들어지면 그 수를 이용하여 순열을 만듬
            return;
        }

        for (int i=start; i<=end && end-i+1 >= r-index; i++)
        {
            data[index] = arr[i];
            combinationUtil(arr, data, i+1, end, index+1, r);
        }
    }

    void myswap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    void permutation(int[] arr, int d, int n, int r) {
        if (r == 0) {
            int num = makeNum(arr, d);
            if(isDecimal(num)) {  // 해당 순열이 구성되면 소수인지 체크
                numSet.add(num);  // 소수가 맞으면 set(중복 수가 있으므로)에 집어넣음
            }
            return;
        }
        for (int i = d; i < n; i++) {
            myswap(arr, d, i);
            permutation(arr, d + 1, n, r - 1);
            myswap(arr, d, i);
        }
    }

    private boolean isDecimal(int num) {
        if(num < 2) return false;
        for (int i = 2; i < num; i++) {
            if(num % i == 0) return false;
        }
        return true;
    }

    private int makeNum(int[] arr, int d) {
        int num = 0;
        for (int i = 0; i < d; i++) {
            if(i > 0) num *= 10;
            num += arr[i];
        }
        return num;
    }

}