[JAVA] 완전탐색 "소수 찾기"

완전탐색을 이용하여 소수를 찾는 알고리즘이다.

이전에 String을 parseInt하는 부분도 포함되어있는 문제다.

 

그리고, Permutation순열을 이용하여 수학적으로 재귀탐색을 하는 방식이며,

Set을 이용하여 중복 제거를 하는 방식으로 알고리즘을 풀어야 했다.

 

 

필자는 Permutation부분을 스스로 구현하기 어려워 다른 이의 코드를 참고하였다.

codevang.tistory.com/299?category=827588

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

class Solution {
    private static TreeSet<String> set = new TreeSet<>();
    private int count;

    public static boolean check_prime_num(int num) {
        if(num==1) return false;

        if ( num == 2) return true;

        if (num % 2 == 0) return false;

        int prime_sqrt = (int) Math.sqrt(num);
        for (int i = 3; i <= prime_sqrt; i += 2) {
            if (num % i == 0) {
                return false;//소수가 아닌경우 false
            }
        }
        return true;//소수인경우 true
    }

    public void permutation(List<Character> arr, List<Character> result, int n, int r) {
        if (r == 0) {//nP0일때

            if (result.get(0) != '0') {//결과값에서 0인덱스의 값이 0이 아닐때(이미 값이 있으면)
                String str = "";
                int size = result.size();
                for (int i = 0; i < size; i++) {
                    str += result.get(i);//값들을 불러와서 str에 다 이어붙여
                }

                int num = 0;

                if (!set.contains(str)) {//set에 해당 문자열이 포함되어있지 않으면
                    num = Integer.parseInt(str);
                    set.add(str);//set에 그 숫자를 추가한다.

                    //소수판별
                    if (check_prime_num(num)) {//해당 숫자가 소수이면
                        System.out.println(num);
                        count++;//카운트값 올려
                    }
                }
            }

            return;
        }
        //무조건 실행
        for(int i =0; i<n; i++){
            result.add(arr.remove(i));//결과값에 받은 arr의 값을 0~n(arr사이즈)까지 쭉
            permutation(arr, result, n-1, r-1);//permutation을 재귀로 n-1 r-1을 넣어서 실행
            arr.add(i, result.remove(result.size() - 1));
        }
    }

    public int solution(String numbers) {
        int size = numbers.length();

        List<Character> arr = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arr.add(numbers.charAt(i));
        }
        List<Character> result = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            permutation(arr, result, size, i + 1);
        }


        return count;
    }
}

class의 내부에 전역변수로 TreeSet을 선언했다.

경우의 수가 많아지면 Set에서 검색하는 빈도수가 많아질테니, HashSet보다는 정렬해서 저장하는 TreeSet이 더 적합하다고 한다. TreeSet은 저장할 때는 좀 더 오래걸리지만 검색할 때는 더 빠릅니다.

 

크게 메소드는 solution, check_prime_num, permutation 부분이다.

check_prime_num은 소수인지 확인하는 부분인데, 이는 비교적 구현하기 쉬웠다.

계산의 효율성을 위해서 개선하는데에 더 노력을 들였다.

 

소수의 조건

• 1은 소수가 아니고, 2는 소수이다.
• 짝수면 소수가 아니다.
• 수를 '1~해당수의 제곱근 ' 까지 나눴을때 나머지가 0인경우가 없으면, 해당 수는 소수이다.

이런 방식으로 check_prime_num을 구현하였다.

 

 

다음은 solution 부분이다.

 

두개의 LinkedList를 선언해서 arr에는 널려있는 카드를,

result에는 뽑은 카드를 넣는다고 가정하였다.

 

그리고 for문을 통해 nP1 + nP2 + ...+ nPr + ... + nPn 값을 구한다.

카드 n개중에 1개만 뽑아서 수를 만든값, 2개를 뽑아서 수를 만든 값, ... , r개를 뽑아서 수를 만든 값,

..n개를 뽑아서 수를 만든값을 더하는 것이다.

 

 

다음은 permutation 부분이다.

 

재귀를 통해서 nP0와 같이 r값이 0이 된 경우, result값을 합쳐서 parseInt한다.

해당 값을 set에 넣어서 중복하여 체크하지 않게 하기 위해서,

set에 해당값이 있는지 검사하고, 없으면 해당값을 넣고 check_prime_num을 통해 소수판별하여 소수면 count++한다.

 

아래는 재귀부분이다.

arr에서 값을 하나 빼와서 result에 넣고, (n-1)P(r-1)을 재귀로 돌린다.

n-1은 arr에서 한개를 뺐으니 줄은거고, r-1은 카드를 하나 뽑았으니 나머지 카드를 뽑는 경우를 의미한다.

즉, 카드를 한개씩 뽑아서(동시에 여러장 뽑는게 아니라) 그에 따른 경우의 수를 재귀로 들어간다고 생각하면 된다.

 

 

 

해당 방식을 통해서 답을 구하면 효율이 아주 좋지만 좀 복잡하다.

 

따라서 다른 코드를 찾아보았다.

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

        public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}

이 방식은 substring을 이용해서 i번째 char만 빼고 나머지 값을 str로 넣어주는 방법을 이용했다.

재귀를 할때 i번째 char를 뽑아서 prefix(접두어)로 넣어놓고 재귀를 돌리는방식(n-1)P(r-1)과 같은 방식으로 진행했다.

 

substring(0, i) => 0~i-1번째까지 추출

substring(i+1 , n) => i+1~n번째까지 추출

 

따라서 i 번째 char값만 추출된다.

 

실행시간은 위의 코드보다 아래의코드가 더 오래걸리지만 보기에 간결하다는 장점이 있다.