190108 완전탐색 (2) 소수 찾기

2019-01-08

완전탐색 (2) 소수 찾기

문제 설명

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

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

제한사항
  • numbers는 길이 1 이상 7 이하인 문자열입니다.
  • numbers는 0~9까지 숫자만으로 이루어져 있습니다.
  • 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbers return
17 3
011 2
입출력 예 설명

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

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

  • 11과 011은 같은 숫자로 취급합니다.
풀이 과정
  • (생성할 수 있는 최소값,최대값)범위의 소수목록을 구하고,
  • (생성할 수 있는 모든 숫자)를 구해서 소수목록에 그 숫자가 있으면 answer++
import java.util.*;
public class Permutation{
     public void doCombination(ArrayList<String> t, String[] comb, String[] arr, int n, int r, int index, int target){
        if(r==0){
            doPermutation(t,comb,0);
        }else if(target==n) return;
        else{
            comb[index]=arr[target];
            doCombination(t,comb,arr,n,r-1,index+1,target+1);
            doCombination(t,comb,arr,n,r,index,target+1);
        }
    }
    public void doPermutation(ArrayList<String> t, String[] arr, int startIdx){
        int len=arr.length;
        if(startIdx==len){
            String tmp="";
            for(int i=0;i<arr.length;i++)
                tmp+=arr[i];
            t.add(tmp);
            return;
        }
        for(int i=startIdx;i<len;i++){
            swap(arr,startIdx,i);
            doPermutation(t,arr,startIdx+1);
            swap(arr,startIdx,i);
        }
    }
    public void swap(String[] arr, int n1,int n2){
        String tmp=arr[n1];
        arr[n1]=arr[n2];
        arr[n2]=tmp;
    }
}
class Solution {
        public static ArrayList<Integer> primeList(int start,int end){
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=start;i<=end;i++){
            boolean isPrime=true;
            for(int j=2;j<=(int)Math.sqrt(i);j++){
                if(i%j==0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime && i>1)
                list.add(i);
        }

        return list;
        }
    public int solution(String numbers) {
        int answer=0;
        int idx=0;
        Permutation ex=new Permutation();
        String[] s=numbers.split("");

        ArrayList<String> t1=new ArrayList<>();
        ArrayList<Integer> t2=new ArrayList<>();

        for(int i=0;i<s.length;i++){
            String[] comb=new String[i+1];
            ex.doCombination(t1,comb,s,s.length,i+1,0,0);
        }

        for(String tmp:t1)
            t2.add(Integer.parseInt(tmp));

        HashSet h=new HashSet(t2);
        t2.clear();
        t2.addAll(h);
        Collections.sort(t2);
        int size=t2.size();
        int end=t2.get(size-1);
        ArrayList<Integer> pList=primeList(t2.get(0),end);
        for(int i=0;i<size;i++){
            if(pList.indexOf(t2.get(i))!=-1)
                answer++;
        }

        return answer;
    }
}
  • 완전탐색….정말 아이디어 내는방법도 모르겠고 코딩도 힘겹고!!ㅜㅜ