[프로그래머스] Level2 소수 찾기 (Java)

문제 링크

문제

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

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

핵심

주어진 numbers를 순열로 뽑되 "1~numbers의 길이"개 만큼 뽑도록 반복해서 확인해줘야 했다.

코드

import java.util.*;

class Solution {
    
    static boolean[] visited;
    static int answer;
    static int[] perm_num;
    static Set<Integer> set;
    
    static boolean check(int num) { // 3
        if(num<2) return false;
        for(int i=2; i<=Math.sqrt(num); i++) {
            if(num%i==0) return false;
        }
        return true;
   }
    
    static void permutation(String numbers, int cnt, int n) {
        
        if(cnt==n) {
            int num = 0;
            for(int i=0; i<numbers.length(); i++) { 
                num += perm_num[i]*Math.pow(10,i);
            }
            if(check(num)) set.add(num); // 3
            
            return;
        }
        
        for(int i=0; i<numbers.length(); i++) { // 2
            if(!visited[i]) {
                visited[i] = true;
                perm_num[cnt] = numbers.charAt(i)-'0';
                permutation(numbers,cnt+1,n);
                visited[i] = false;
            }
        }
        
    }
    
    public int solution(String numbers) {
        answer = 0;
        set = new HashSet<>();
        
        for(int i=1; i<=numbers.length(); i++) { // 1
            visited = new boolean[numbers.length()];
            perm_num = new int[numbers.length()];
            permutation(numbers,0,i);
        }
        
        answer = set.size(); // 4
        return answer;
    }
}

1. "1~numbers의 길이" 개 만큼 뽑기 위해 순열을 구하는 메서드를 numbers 길이 만큼 반복한다.
2. numbers의 모든 자릿수를 탐색하며 순열을 구한다.
3. 현재 뽑아야할 갯수(n)만큼 뽑았으면 해당 숫자가 소수인지 아닌지 판별하고, 소수라면 중복을 제거하기 위해 set에 추가한다.
4. 모든 연산이 끝나면 set의 size가 만들 수 있는 소수의 갯수가 된다.