(Java)프로그래머스 코딩테스트 연습 - 완전탐색 - 소수 찾기

1. 문제

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

코딩테스트 연습 - 소수 찾기

2. 나의 풀이

import java.util.*;

class Solution {
    
    ArrayList <Integer> all_number = new ArrayList<>();
    String number = "";
    
    public int solution(String numbers) {
        int answer = 0;
        String [] numbers_split = numbers.split("");
        Arrays.sort(numbers_split);
        int len = numbers_split.length;
        boolean [] visited = new boolean[len];
        //System.out.println(Arrays.toString(visited));
        
        System.out.println(Arrays.toString(numbers_split));
        
        for(int i = 1; i <= len; i = i + 1) {
        	gyeongwoo(numbers_split, visited, len, i);
        }
        
        System.out.println(all_number);
        //System.out.println(Arrays.toString(visited));
        //System.out.println(Integer.parseInt("01"));
        for(int imsi : all_number) {
        	if(isPrime(imsi)) {
        		answer += 1;
        		System.out.println("imsi : " + imsi + ", answer : " + answer);
        	}
        }
        return answer;
    }
    
    //배열과 자릿 수가 매개변수로 주어질 때 해당 자릿 수로 나올 수 있는 모든 매개변수를 ArrayList에 
    //저장하는 메소드
    void gyeongwoo(String [] numbers_split, boolean [] visited, int len, int i){
    	if(i == 0) {
    		if(Integer.parseInt(number) == 0) {
    			
    		}else if(!all_number.contains(Integer.parseInt(number))) {
        		System.out.println(number);
        		all_number.add(Integer.parseInt(number));
    		}
    	}
    	
    	for(int j = 0; j < len; j = j + 1) {
    		if(visited[j] == true) {
    			continue;
    		}else if(visited[j] == false) {
    			visited[j] = true;
    			number += numbers_split[j];
    		}
    		gyeongwoo(numbers_split, visited, len, i - 1);
    		visited[j] = false;
    		number = number.substring(0, number.length()-1);
    	}
    }
    
    // 소수인지 확인하는 메소드
    boolean isPrime(int number) {
    	if(number == 1) {
			return false;
		}else if(number == 2) {
			return true;
		}
    	for(int i = 2; i <= Math.sqrt(number); i = i + 1) {
    		if(number % i == 0) {
    			return false;
    		}
    	}
    	return true;
    }
}

3. 다른 사람 풀이

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

    }

}