프로그래머스 소수 찾기 Java 풀이

기존 풀이

import java.util.LinkedList;

class Solution {
    static int numberArray[];
    static int ans[] = new int[9999999];
    static int answer = 0;
    public int solution(String numbers) {
        numberArray = new int[numbers.length()];
        for(int i=0; i<numberArray.length; i++){
            numberArray[i] = Integer.parseInt(numbers.charAt(i)+"");
        }

        int n = numberArray.length;
        for(int i=1; i<=numberArray.length; i++){
            LinkedList<Integer> perArr = new LinkedList<Integer>();
            int[] perCheck = new int[n];
            permutation(n, i, perArr, perCheck);
        }

        return answer;
    }

    public void permutation(int n, int r, LinkedList<Integer> perArr, int[] perCheck) {
        if(perArr.size() == r){
            String tmpNum ="";
            for(int i : perArr){
                tmpNum += numberArray[i]+"";
            }

            if(ans[Integer.parseInt(tmpNum)] == 0){
                if(checkPrime(Integer.parseInt(tmpNum)) == 2){
                    answer++;
                }
            }
            ans[Integer.parseInt(tmpNum)] = 1;

            return;
        }

        for(int i=0; i<n; i++){
            if(perCheck[i] == 0){
                perArr.add(i);
                perCheck[i] = 1;
                permutation(n, r, perArr, perCheck);
                perCheck[i] = 0;
                perArr.removeLast();
            }
        }

    }

    public int checkPrime(int num) {
        if(num == 1 || num == 0)return 1;
        for(int i=2; i<num; i++){
            if(num%i == 0){
                return 1;
            }
        }
        return 2;
    }
}

https://limkydev.tistory.com/200 이 분의 풀이이다.

 

다른 사람의 풀이

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);

    }

}