[240525] 알고리즘 리부트 60일차 - 프로그래머스 소수 찾기 자바

처음에는 문제 그대로 숫자를 배열 만든 후, 재귀를 통해 수를 만들어내고 (1의 자리 수부터 최대 길이 수까지) 해당 수가 소수인지를 판별하려 했다. 하지만 그 대신 소수일 가능성이 있는 2~9999999까지 수를 순회하며 소수 여부를 판별하고 해당 수를 내가 가진 숫자 풀에서 만들 수 있는지 판별하는 방식으로 구현했다. 

여기서 소수 여부를 판별할 때 2부터 타겟 숫자의 제곱근까지의 수로 나누어 떨어지는지 확인하는데 타겟 수 자체가 아닌 그 수의 제곱근까지만 보는 이유는 target이 될 수 있는 가능한 수는 target의 제곱근 * target의 제곱근이기 때문에 이보다 커지면 해당 수를 넘는 값이 나오게 된다. 둘 중 한 수가 target의 제곱근보다 크다면 나머지 한 수는 반드시 target의 제곱근보다 작을 것이다. 

36을 예시로 들어보자면, "1,36(소수는 1과 자기 자신만으로 나누어 떨어지는 수, 따라서 이 조합은 판단 대상 범위 밖) / 2,18 / 3,12 / 4,9 / 6,6" 의 쌍으로 만들어지는데 둘 중 한 수가 36의 제곱근인 6보다 항상 작음을 알 수 있다. 따라서 제곱근까지만 확인하더라도 나누어 떨어지는 수가 있어 소수가 아님을 판단할 수 있는 것이다.

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;        
        
        String[] each = numbers.split("");
        
        int [] numCnt = new int [10];
        
        for(String s : each)            
            numCnt[Integer.parseInt(s)]++;
        
        for(int i = 2; i<10000000; i++){
            
            if(isPrimeNum(i) && isPossible(numCnt, i)) answer++;
        }          
        
        return answer;
    }
    
    private static boolean isPrimeNum(int target){
        
        for(int i = 2; i <= Math.sqrt(target); i++){
            if(target%i==0) return false;
        }
        
        return true;
    }
    
    private static boolean isPossible(int[] pool, int target){
        
        int[] temp = pool.clone();     
        
        while(target>0){
            
            
            if(temp[target%10] == 0) return false;
            
            temp[target%10]--;
            
            target/=10;
            
        }
        
        return true;
         
    }
}