Programmers > 완전탐색 > #26 소수찾기(level 2) [JAVA]

소수 찾기 (Level 2)

 

 

1. 문제 설명

 

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

 

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

 

 

 

2. 나의 코드

 

- 소수를 구하기 전에 주어진 문자열에서 만들 수 있는 모든 순열을 찾아야 한다.(이게 난이도 헬...)

- 1~numbers.length 까지 for문을 돌면서 각 숫자에 맞는 조합을 우선 찾고,

- 그 조합을 permutation 메소드에 넣어서 순서가 있는 순열을 찾는다.

- HashSet을 이용하여 중복을 제거해주고!

- 그 다음 소수인지 아닌지 판별한다!!!

- 조합과 순열 메소드는 다음 홈페이지 참고!!

1) https://onsil-thegreenhouse.github.io/programming/algorithm/2018/04/05/permutation_combination/

2) http://gorakgarak.tistory.com/522

 

import java.util.*;
import java.lang.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        int index = 0;
        Permutation ex = new Permutation();
        String [] s = numbers.split("");
        ArrayList <String> t = new ArrayList<String>();
        ArrayList <Integer> t2 = new ArrayList <Integer>();
        
        for(int i=0;i<s.length ;i++){
            String [] combArr = new String[i+1];
            ex.doCombination(t,combArr,s,s.length,i+1,0,0);
        }
        System.out.println(t.toString());
        
        for(String ss : t){
            t2.add(Integer.valueOf(ss));
        }
        
        HashSet hm = new HashSet(t2);
        t2.clear();
        t2.addAll(hm);
        
        //search for prime number
        for(int num=0; num < t2.size();num++){
            int number = t2.get(num);
            if(number == 1)
                t2.set(num,0);
            for(int p=2; p <number;p++){
                    if(number%p == 0){
                        t2.set(num,0);
                        break;
                    }
            }
        }
        
        for(int i=0;i<t2.size();i++){
            if(t2.get(i) != 0){
                answer++;
            }
        }
        return answer;
    }
}
class Permutation{
   public void doCombination(ArrayList <String> t,String[] combArr, String[] arr, int n, int r, int index, int target){
        if(r == 0){
            //to-do: combArr permutation
            doPermutation(t,combArr, 0);
        }else if(target == n) return;
        else{
            combArr[index] = arr[target];
            // System.out.println(Arrays.toString(combArr));
            doCombination(t,combArr, arr, n, r-1, index+1, target+1);
            doCombination(t,combArr, arr, n, r, index, target+1);
        }
    }

    public void doPermutation(ArrayList<String> t,String[] arr, int startIdx){
        int length = arr.length;
        if(startIdx == length){
            String temp = "";
            for(int i=0;i<arr.length;i++){
                temp += arr[i];
            }
            t.add(temp);
            return;
        }
        for(int i=startIdx; i<length; i++){
            swap(arr, startIdx, i);
            doPermutation(t,arr, startIdx+1);
            swap(arr, startIdx, i);
        }
    }

    public void swap(String[] arr, int n1, int n2){
        String temp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = temp;
    }
}

 

 

3. 다른사람 코드

 

 

- 조합과 순열을 한번에 그리고 단 몇줄에 끝내버릴 수도 있다...

 

public void func(String s, String number) {
        if (number.length() == 0) {
            if(!s.equals(""))
                ts.add(Integer.parseInt(s));
        } else {
            for (int i = 0; i < number.length(); i++) 
                func(s + number.charAt(i), number.substring(0, i) + number.substring(i + 1, number.length()));
            for (int i = 0; i < number.length(); i++) 
                func(s , number.substring(0, i) + number.substring(i + 1, number.length()));
        }
    }