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

 

 

 

모든 조합 + 순열을 확인해야하는 문제다. 

 

numbers 의 길이가 최대 7개 이므로 최대 경우의 수는  7 + 7*6 + 7*6*5 + 7*6*5*4+7*6*5*4*3 + 7*6*5*4*3*2 + 7*6*5*4*3*2*1 =13699이다. 완전 탐색해도 1초 안에 확인할 수 있는 충분한 경우의 수다.

 

 

만약 카드가 1~5까지 5장이 있다고 가정하자. 모든 경우를 탐색하는 DFS를 구현해본다.

 

아래의 경우의 수는 모든 경우의 수 가지들 중에 일부 가지들이다.

 

1. 첫번째 자리 ( 모든 한자리 수 검사)

한 자리수의 경우는 1에서 5까지 수 중에서 1가지를 선택할 수 있다. 총 5가지 경우의 수가 있다.

 

1부터 5까지 숫자를 하나씩 소수인지 아닌지 검사한다. 소수가 맞다면 소수만 모아두는 Set에 넣어둔다. 

 

Set인 이유는 중복된 소수를 거르기 위해서다.

 

2. 두번째 자리 ( 모든 두자리수 검사)

 

만약 1을 선택했다면? 즉 visited[1] = true를 한다면 두번째 자리의 후보는 2부터 5까지가 될것이다.

따라서 12,13,14,15 중에 소수인지 아닌지 검사하고 소수라면 Set에 넣어둔다.

3. 세번째 자리 (모든 세자리수 검사)

 

두번째 자리에서 3을 선택했다면  즉 visited[3]= true로 하고 다음 dfs로 넘어간다.

세번째 자리에서 해당되는 후보는 2,4,5 이다. 

따라서 132,134,135가 소수인지 아닌지 검사하고 소수라면 Set에 넣어둔다.

 

 

 

4. 네번째 자리 (모든 네 자리수 검사)

3번째 자리에서 2를 선택했다면 (visited[2]=true) 후보는 4,5 두개가 남는다.

1324, 1325 가 소수인지 아닌지 검사하고 소수라면 Set에 넣어둔다.

 

 

5. 다섯번째 자리( 모든 다섯자리 검사)

5를 선택했다면 남은 후보는 4 한개이다.

그래서 13254가 소수인지 아닌지 판별후 소수라면 Set에 넣어둔다.

 

 

 

 

자바 코드

 

import java.util.*;
class Solution {
    static Set<Integer> answerSet = new HashSet<>();
    static char[] arr;
    static int n;
    
    public int solution(String numbers) {
        arr = numbers.toCharArray();
        n = arr.length;
        
        boolean[] visited = new boolean[n];
        String sum = "";
        dfs(0,visited,sum);
        
        return answerSet.size();
    }
    
    public void dfs(int idx,boolean[] visited,String sum){
        int tmp = (sum.equals(""))?0:Integer.parseInt(sum);
        if(isPrime(tmp)) answerSet.add(tmp);
        if(idx == n){
            return;
        }
        else{
            for(int i=0;i<n;i++){
                if(visited[i]==false)
                {
                    visited[i]=true;
                    String str = sum + (arr[i]-'0');
                    dfs(idx+1,visited,str);
                    visited[i]=false;
                }
            }
            
        }   
    }

    public boolean isPrime(int s){
        if(s < 2) return false;
        for(int i = 2;i<s-1;i++){
            if(s%i==0) return false;
        }
        return true;
    }
}