알고리즘101 :: 프로그래머스 - 소수찾기

소수찾기는 크게 3가지 세션으로 나눠볼 수 있습니다. 

1) 주어진 number를 문자로 쪼개기
2) 문자로 쪼갠것으로 모든 경우의 수를 만들기
3) 에라토스테네스체를 이용해 소수인지 검증하기 

1의 경우에는 

String str = "17" 인경우 
String[] number = str.split("") 이용해서 1, 7로 쪼갤 수 있습니다. 

2의 경우에는 

string[] number, boolean[] picked, StringBuilder sb 를 활용합니다. 
number는 1의 경우에서 구한것이므로 넘어가고
boolean[] picked = new boolean[number.length]; 로 선언
StringBuilder sb = new StringBuilder() 로 선언
HashSet<Integer> dff = new HashSet<>(); //중복되는 케이스를 방지. 만들 수 있는 경우를 모두 담을것임

make(number, picked, sb) 로 함수를 실행합니다. 

int len = picked.length; //체크해야할 문자의 길이를 확인해보기 위함
int result = true; //picked에서 모두 true인지 false인지 확인하기 위함
for(boolean flag : picked){
       if(!flag){ //아직 방문하지 않은 문자가 존재하는 경우이므로
             result = false; //이후에 true 상태에서 return 하기 때문에 여기서는 false 로 대입
             break;
      }
}
if(result) return; //모두 방문하였으므로 확인하지 않아도 됌
for(int i=0; i<len; i++){ //길이 모두를 확인 
         if(!picked[i]){ //실행할때는 아직 방문하지 문자를 확인해야 합니다. 그래야 모든 경우를 만들 수 있습니다.
                sb.append(number[i]); //number 의 i번째 위치를 가져오고
                dff.add(Integer.parseInt(sb)); //정수형으로 선언해서 변환 
               picked[i] = true; //백트래킹, 방문했으므로 true
               make(number, picked, sb); //재귀
               picked[i] = false; //백트래킹, 방문해제 false
              sb.deleteCharAt(sb.length()-1); //sb 마지막에 있는 엘리먼트 삭제
}
}
마지막에서는 에라토스테네스체로 소수를 검증합니다.
for(int i=2; i<=num/2; i++) //반만 확인해도 됩니다. 그 이후부터는 배수관계
   for(int j=2; j*i<=num; j++) 
          NUMBER[i*j] = false; //자기자신 외에도 숫자가 존재하므로 소수가 아닙니다. 
return NUMBER[num]; //num은 파라미터, 소수를 알아볼 숫자, num까지 확인하게 되면 현재 num값에서 false 인지 true인지 확인할 수 있습니다. 

 

import java.util.*;
class Solution {
    static HashSet<Integer> appendix = new HashSet<>();
    public int solution(String numbers) {
        int answer = 0;
        String[] number = numbers.split("");
        boolean[] picked = new boolean[number.length];
        StringBuilder sb = new StringBuilder();
        make(number, picked, sb);
        boolean[] NUMBER = new boolean[10000000];
        Arrays.fill(NUMBER, true);
        NUMBER[0] = NUMBER[1] = false;
        for(int s : appendix){
            if(dd(s, NUMBER))
                answer+=1;
        }
        
        return answer;
    }
    static boolean dd(int num, boolean[] NUMBER){
        for(int i=2; i<=num/2; i++){
            for(int j=2; j*i<=num; j++){
                  NUMBER[j*i] = false;
            }
        }
        return NUMBER[num];
    }
    static void make(String[] number, boolean[] picked, StringBuilder sb){
        int len = picked.length;
        boolean result = true;
        for(boolean flag : picked){
            if(!flag){
                result = false;
                break;
            }
        }
        if(result) return ;
        for(int i=0; i<len; i++){
            if(!picked[i]){
                sb.append(number[i]);
                appendix.add(Integer.parseInt(sb.toString()));
                picked[i] = true;
                make(number, picked, sb);
                picked[i] = false;
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}