프로그래머스 - 완전탐색 소수찾기 JAVA 자바

Idea

1. String을 split해서 배열에 넣어준다

2. 배열에서 1개부터 - length까지의 개수의 조합을 찾아낸다. -> perm(arr, depth, k)

 

k: 조합할 숫자의 개수 (개수니까 k는 1부터 시작해야한다)
depth: 현재 depth (depth는 0부터 시작한다 )

 

3. 소수인지를 판별해서 소수면 set에 저장해준다. => 소수판별은 sqrt를 사용하였는데 제곱근까지만 돌려보면 알 수 있다고 한다!궁금하면 검색해보길..

 

여기서 같은 숫자가 들어갈 수도 있으니 set에 있는지 없는지를 먼저 확인하고 소수를 판별하였다. (이건 check_prime들어가기전에 체크했음)

판별과정은 밑에 블로그 링크를 달아놨으니 그걸 참고하면 좋을 것 같다..

import java.util.*;
class Solution {
     int answer = 0; 
    Set<Integer> set=new HashSet<>();

    public void check_prime(int num){
        int sqrt_num=(int)Math.sqrt(num);
        boolean flag=true;
        if(num==2)
            flag= true;
        else if(num%2==0||num==1)
            flag= false;
        else{
          for(int i=3;i<=sqrt_num;i+=2){
            if(num%i==0)
                flag= false;
          }
        }
        if(flag){
            set.add(num);
        }      
    }
    public void perm(String[] arr, int depth, int k){
        if(depth==k){
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<k;i++){
                sb.append(arr[i]);
            }
            int num=Integer.parseInt(sb.toString());
            if(!set.contains(num)){
                check_prime(num); 
            }
        }
        else{
            for(int i=depth;i<arr.length;i++){
                swap(arr,i,depth);
                perm(arr,depth+1,k);
                swap(arr,i,depth);
            }       
        }
    }
    public void swap(String[] arr, int i, int j){
        String temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public int solution(String numbers) {
        String[] str = numbers.split("");
        for(int i=1;i<=str.length;i++){
            perm(str,0,i);  
        }
        int answer=set.size();
        return answer;
    }
}

gorakgarak.tistory.com/522

참고용 (왜 swap을 사용하였는지에 대한 풀이가 나와있음)