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

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

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

 

소수 문제는 에라토스테네스의 체만 안다면 크게 어렵진 않다.

코테를 대비하기 위해 IDE 없이 풀고있는데 이게 제일 어렵다...

 

순서는 다음과 같다.

        1. 에라토스테네스체
        1-2. 7 이하이기 때문에 9999999 보다 작음
        2. 각 문자열을 쪼개서 array로 만든다.
        3. 쪼개진 array를 DFS로 조합하여 소수인지 검사한다.
        4. 체킹

class Solution {
     public int solution(String numbers) {
        net = new boolean[10000000];
        net[0]=true; net[1] = true;
        for(int i=2;i<10000000/2;i++){
            for(int j=i*2;j<10000000;j+=i){
                net[j]=true;
            }
        }
        char[] spt = numbers.toCharArray();

        visit = new boolean[8];
        duplicate = new boolean[10000000];
        result = 0;

        dfs(0,0,numbers.length(),spt,new StringBuilder());
        
        return result;
    }
    static boolean[] net;
    static int result;
    static boolean[] visit;
    static boolean[] duplicate;
    public static void dfs(int s, int num, int limit, char[] arr,StringBuilder now){
        String tmp = now.toString();
        if(!tmp.equals("") && net[Integer.parseInt(tmp)]==false && duplicate[Integer.parseInt(tmp)]==false){
            result++;
            System.out.println(tmp);
            duplicate[Integer.parseInt(tmp)]=true;
        }
        if(now.length() == limit) return;
        else{
            for(int i=0;i<limit;i++){
                if(visit[i]==false) {
                    visit[i] = true;
                    now.append(arr[i]);
                    dfs(i, num + 1, limit, arr, now);
                    visit[i] = false;
                    now.deleteCharAt(now.length() - 1);
                }
            }
        }
    }
}