[프로그래머스 - 소수] 소수 찾기

import java.util.*;

class Solution {
    
    private HashSet<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        
        boolean[] visited = new boolean[numbers.length()];
        StringBuilder sb = new StringBuilder();

        // 종이 조각으로 만들 수 있는 모든 숫자 조합 생성
        generateNumbers(numbers, visited, sb);

        int count = 0;
        
        for (int num : set) {
            if (isPrime(num)) {
                count++;
            }
        }
        return count;
    }
    
    // 종이 조각으로 만들 수 있는 모든 숫자 조합 생성
    private void generateNumbers(String numbers, boolean[] visited, StringBuilder sb) {
        // 숫자 조합을 set에 추가
        if (sb.length() > 0) {
            set.add(Integer.parseInt(sb.toString()));
        }
        // 종이 조각으로 만들 수 있는 숫자 조합 생성
        for (int i = 0; i < numbers.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                sb.append(numbers.charAt(i));
                generateNumbers(numbers, visited, sb);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }
    
    // 소수 판별
    private boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        // 제곱근 이하의 값까지만 검사하면 완료
        // ex) √24 기준
        // 2 * 12 | 3 * 8 | 4 * 6 | √24 * √24 | 6 * 4 | 8 * 3 | 12 * 2
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    
}