소수 찾기[완전탐색]

알고리즘잡스에서 푼 문제중

 

level8 순열 뽑기

앞레벨에서 소수판단(에라스토스체)  

 

두가지 문제 풀었던 골격을 활용

 

<1>

(0,1,2)

(0,2,1)

(1,0,2)

(1,2,1)

이런식으로 인덱스를 나열하는게 필요할테고

<2>

depth가 1일때, 2일때, 3일때 등등 판단 필요

 

체감은 2문제 짬뽕시킨 문제

 

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public static int n;
    public static int[] arr;
    public static boolean[] v;
    public static char[] input;
    public static boolean[] isPrime = new boolean[10000021];
    public static ArrayList<Integer> arrList = new ArrayList<Integer>();
    public static int solution(String numbers) {
        makePrimeTable();
        input = numbers.toCharArray();
        v = new boolean[input.length];
        for(int i=1;i<=numbers.length();i++) 
        {
            n=i;
            arr = new int[n];
            f(0);
        }
//        System.out.println(arrList.toString());
        return arrList.size();
    }


    private static void makePrimeTable() {
        for(int i=0;i<isPrime.length;i++)isPrime[i]=true;
        isPrime[0]=false;
        isPrime[1]=false;

        for(int i=2;i<isPrime.length;i++) 
        {
            for(int j=i+i;j<isPrime.length;j=j+i) 
            {
                isPrime[j]=false;
            }
        }

    }


    private static void f(int depth) {
        if(depth==n) 
        {
//          System.out.println(Arrays.toString(arr));
            findPrime();
            return;
        }

        for(int i=0;i<v.length;i++) 
        {
            if(!v[i]) 
            {
                v[i]=true;
                arr[depth]=i;
                f(depth+1);
                v[i]=false;
            }
        }
    }


    private static void findPrime() {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) 
        {
            sb.append(input[arr[i]]);
        }
        int x = Integer.parseInt(sb.toString());
        if(isPrime[x] && !arrList.contains(x) ) 
        {
            arrList.add(x);
        }


    }


    public static void main(String[] args) {
        System.out.println(solution("011"));
    }
}