Programmers : 소수찾기, 42839번

INPUT & OUTPUT

1. INPUT : 연속숫자(0~9)로 이루어진 문자열
2. OUTPUT : 주어진 숫자로 조합 가능한 전체 경우 중 소수의 갯수

1. 주어진 문자열을 숫자로 parsing

import java.util.*;

class Solution {
    int sols = 0;
    Set<Integer> primes = new HashSet<>();

    public int solution(String numbers) {
        String[] nums = numbers.split("");
        boolean[] isUsed = new boolean[nums.length];
        for(int i=0;i<isUsed.length;i++){
            isUsed[i] = false;
        }
        for(int i=0;i<nums.length;i++){
            boolean[] used = isUsed.clone();
            used[i] = true;
            findNext(nums[i], nums, used);
        }
        return sols;
    }

2. DFS 구현 : 재귀 호출

   하위 노드 탐색 시에 숫자 조합의 순서가 다를 경우 다른 숫자이므로,
   다음 노드 선택시 루프를 돌아 전체 경우를 탐색한다.

    private void findNext(String combString,String[] numbers,boolean[] isUsed){
        int num = Integer.parseInt(combString);
        /**/
        if(isPrime(num) && !primes.contains(num) ){ 
            sols++; 
            primes.add(num);  
        } 
        
        for(int i=0;i<numbers.length; i++){  //하위 노드 탐색 시 순서를 고려한다.
            if(!isUsed[i]){
                boolean[] used = isUsed.clone(); 
                used[i] = true;
                String next = combString+numbers[i];
                findNext(next, numbers, used);    
            }

        }

    }

3. 소수판별 : 제곱근 n 이전의 정수까지만 판별, #에라토스테네스의 체

    private boolean isPrime(int num){
        if(num==0||num==1 ) return false;
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}