소수 찾기(프로그래머스) (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

문제 설명

• 주어진 numbers를 각각 나누어 숫자를 만들 때 소수인지를 검사 하는 것이빈다.
• 17은 7 17 71 3개의 소수를 만들 수 있습니다.

 

문제에 대한 아이디어

숫자가 0 ~ 9 까지이고 numbers의 길이는 1이상 7이하이기 때문에 완전 탐색으로 충분히 해결할 수 있습니다.

numbers로 만들 수 있는 숫자를 다 탐색하면서 소수인지 검사하면 됩니다.

 

전체 코드

import java.util.*;

class Solution {
    //소수 인지 판별
    private boolean isPrime(int n){
        if(n <= 1) return false;
        for (int i = 2; i * i <= n; ++i){
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public void getPrimes(int now, int[] numbers, boolean[] isUsed, Set<Integer> primes){
        if(isPrime(now)) primes.add(now); // 현재 숫자가 소수이면 저장
        for(int i = 0; i < numbers.length; ++i){ // 백트래킹으로 모든 숫자 탐색
            if(isUsed[i]) continue;
            isUsed[i] = true;
            int next= now*10 + numbers[i];
            getPrimes(next, numbers,isUsed,primes);
            isUsed[i] = false;
        }
    }
    public int solution(String nums) {
        Set<Integer> primes = new HashSet<>();
        int[] numbers = nums.chars().map(c -> c - '0').toArray();
        getPrimes(0, numbers, new boolean[numbers.length], primes);
        return primes.size();
    }  
}