프로그래머스_소수 찾기(JAVA)

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

프로그래머스

[문제 풀이]

완전탐색을 이용하여 문제를 풀었습니다.

 

완전탐색으로 순열과 에라토스테네스의 체를 이용하였습니다. 구현한 방식은 아래와 같습니다.

1. 나올 수 있는 모든 숫자를 뽑기 위해 순열을 이용하여 숫자를 만들어 주었습니다.
2. 순열을 구현한 방식은 만들 숫자의 길이 r를 정해주고 뽑은 숫자를  boolean 배열에 적어주며 뽑은 숫자의 길이가 r과 같아지면 에라토스테네스의 체를 이용하여 소수인지 판별을 해주었습니다.

[JAVA]

import java.util.HashSet;
import java.util.Set;

class Solution{
	
    Set<Integer> numberSet = new HashSet<>();
	
    public int solution(String numbers) {
        int answer = 0;
        int n= numbers.length();
        
        char[] numberArray = numbers.toCharArray();
        char[] outputArray = new char[n];
        boolean[] visited = new boolean[n];
        
        for(int i = 1; i <= n; i++) {
        	permutation(numberArray, outputArray, visited, 0, n, i);
        }
        
        return numberSet.size();
    }
    
    public void permutation(char[] number, char[] output, boolean[] visited, int depth, int n, int r){
    	if(depth == r) {
    		String temp = new String(output);
    		
    		if(temp.equals(new String("0")))
    			temp = temp.replaceFirst("^0+(?!$)", "");
    		
            if(isPrime(Integer.parseInt(temp.trim())))
            	numberSet.add(Integer.parseInt(temp.trim()));
    		return;
    	}
    	
    	for(int i = 0; i < n; i++) {
    		if (visited[i] != true) {
                visited[i] = true;
                output[depth] = number[i];
                permutation(number, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
    	}
    }
    
    public boolean isPrime(int num) {
        if (num == 0 || num == 1)
            return false;

        int lim = (int)Math.sqrt(num);

        for (int i = 2; i <= lim; i++)
            if (num % i == 0)
                return false;

        return true;
    }
}