프로그래머스 level2 소수찾기

• 소수 찾기

• darklight

  sublimevimemacs

  Java 

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

 

 

나의코드

 

import java.util.HashSet;
class Solution {
       static int cnt =0 ;
        static HashSet<Integer> hash = new HashSet<Integer>();
public int solution(String numbers) {
      
        String tmp[]  = numbers.split("");
        int arr[] = new int[tmp.length];
        int n = numbers.length();
        for(int i = 0 ;i < tmp.length;i++) {
        	arr[i] = Integer.parseInt(tmp[i]);
        }
		for(int i = 1; i <= n; i ++) {
			int[] output = new int[n];
			boolean[] visited = new boolean[n];
			perm(arr, output, visited, 0, n, i);
			
		}
        
        //여기서 배열을 순열을 만들어서 depth 단계마다 소수인지 판단하여 소수이면 개수를 증가시킨다.
        
        
        return hash.size();
    }
	
    static void perm(int[] arr, int[] output, boolean[] visited,int depth,int n,int r){
    		if(depth == r) {
    		print(output,r);
    		}
    	
    	for(int i = 0 ;i < n ;i++) {
    		if(visited[i] != true) { // 방문안했으면 실행
    			visited[i] = true;  //방문했다
    			output[depth] = arr[i];  //depth 가 1일 때 는 1개만 채워놓고 다시 재귀 
    			perm(arr,output,visited,depth+1,n,r);
    			visited[i] = false;
    			
    		}
    		
    	}
    }
    static void print(int[] arr, int r) {
    	StringBuilder sb = new StringBuilder();
    	for(int i = 0 ; i<r;i++) {
    		sb.append(arr[i]);
    	}

    	
        int num = Integer.parseInt(sb.toString());
        
        for(int i = 2; i < Math.sqrt(num)+1;i++) {
            if(num ==2 || num ==3) {
        		hash.add(num);
        		break;
        	}
            
        	if(num%i ==0 ||  num ==1 ||num ==0) {
        		break;
        	}else if(i ==(int)Math.sqrt(num)) {
                hash.add(num);
                    

        	}
        }
        
        
    
    }
}

 

 

풀이과정