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

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

풀이

 소수 관련 문제를 접할때 마다 사용하는게 아라토니스체의 풀이방법이다. 상당히 효과적이고 범위가 크지 않을경우 빠르게 문제를 해결할 수 있었기에 한* 코딩테스트에서 소수 문제를 만났을 때 빠르게 사용하여 풀이를 진행 하였다. 물론 단순하게 소수문제만 나오는건 아니였지만 이 문제 처럼 섞어서 나왔는데 정확하게 어떤 문제였는지는  다음에 알아보자  소수판별은 에라토스테네스 체 사용하였고 숫자를 이어 붙이는 과정은 순열을 사용하여 풀이를 진행하였다. 관련 테크닉은 따로 포스팅을 할 계획이라... 하긴 해야하는데 아놔... 주2일 근무하면 열심히 블로그 작업 할 자신있는데 주5일 근무하고 2일 황금같은 시간을 와우 클래식에만 안태웠어도 블로그가 벌써 번창 했을 느낌이다. 
언제인가 첨부할 알고리즘 방법론을 뒤로하고 포스팅을 마친다.

 

import java.util.Arrays;
import java.util.LinkedList;

public class Solution {
    static boolean[] checked;
    static int [] primeset;
    static String[] numbers_arr;
    public static int solution(String numbers) {
        primeset=new int[10000000];
        checked=new boolean[10000000];

        for(int i=2;i*2<10000000;i++) {
            if(!checked[i])
            {
                for(int j=i*2;j<10000000;j+=i) {
                    checked[j]=true;
                }
            }
        }
        checked[0]=true;
        checked[1]=true;
        numbers_arr=new String[numbers.length()+1];
        for(int i=1;i<=numbers.length();i++){
            numbers_arr[i]=numbers.substring(i-1,i);
        }

        for(int i=1;i<=numbers.length();i++){
            int[] check = new int[numbers.length()+1];
            LinkedList<String> rCom=new LinkedList<>();
            rePermutation(numbers.length(),i,rCom,check);
        }



        long result=Arrays.stream(primeset).filter(x -> x==1).count();
        int answer = (int)result;
        return answer;
    }
    private static void rePermutation(int n, int r, LinkedList<String> rCom, int[] check) {
        if(rCom.size() == r){
            String result ="";
            for(String i : rCom)
                result+=i;
            int comp=Integer.parseInt(result);
            if(!checked[comp]){
                primeset[comp]=1;
            }
            return;
        }

        for(int i=1; i<=n; i++){
            if(check[i] == 0){
                check[i] = 1;
                rCom.add(numbers_arr[i]);
                rePermutation(n, r, rCom, check);
                check[i] = 0;
                rCom.removeLast();
            }
        }

    }


}