[lv.2] 소수 찾기

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

• 문제
  한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
  각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

• 풀이
  1) 에라스토테네스의 채를 통해 소수로 판별할 수 있는 boolean[]을 만든다.
  2) DFS를 통해 만들 수 있는 모든 수를 조합한다.
  3) 그렇게 나온 수들을 boolean[]으로 체크하여 카운팅한다.

• 코드

import java.util.*;

class Solution {
    static boolean[] prime;
    static boolean[] check;
    static HashSet<Integer> set = new HashSet<>();
    public int solution(String str) {
        int cnt = 0;
        prime = new boolean[(int)Math.pow(10, str.length())+1];
        setPrime();
        check = new boolean[str.length()];
        dfs(str, "", 0);
        Iterator<Integer> iter = set.iterator();
        while(iter.hasNext()){
            int now = iter.next();
            if(!prime[now]) cnt++;
        }
        return cnt;
    }
    static void dfs(String str, String s, int depth){
        if(depth == str.length()) return;
        for(int i=0; i<str.length(); i++){
            if(!check[i]){
                check[i] = true;
                set.add(Integer.parseInt(s+str.charAt(i)));
                dfs(str, s+str.charAt(i), depth+1);
                check[i] = false;
            }
        }
    }
    static void setPrime(){
        prime[0] = prime[1] = true;
        for(int i=2; i*i<prime.length; i++){
            if(!prime[i]){
                for(int j=i*i; j<prime.length; j+=i){
                    prime[j] = true;
                }
            }
        }
    }
}