[프로그래머스/자바] 소수찾기 - DFS

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

프로그래머스

 

 

import java.util.*;
 
public class Solution {
    // 주어진 문자열에 포함된 숫자들로 만들 수 있는 소수의 개수를 반환하는 메서드
    public int solution(String numbers) {
        // 소수를 찾는 메서드를 호출하고 결과 집합의 크기를 반환
        Set<Integer> primeNumbers = findPrimeNumbers(numbers);
        return primeNumbers.size();
    }
    
    // 주어진 문자열에 포함된 숫자들로 만들 수 있는 소수를 찾아 집합에 저장하는 메서드
    private Set<Integer> findPrimeNumbers(String numbers) {
        // 소수를 저장할 HashSet 생성
        Set<Integer> primeNumbers = new HashSet<>();
        // 순열을 구하고 소수인 경우 집합에 추가
        permutation("", numbers, primeNumbers);
        
        return primeNumbers;
    }
    
    // 주어진 문자열의 순열을 구하고, 해당 순열이 소수인 경우 집합에 추가하는 메서드
    private void permutation(String prefix, String str, Set<Integer> primeNumbers) {
        int n = str.length();
        // prefix가 비어있지 않으면, 정수로 변환하여 소수 판별
        if (!prefix.isEmpty()) {
            int num = Integer.parseInt(prefix);
            if (isPrime(num)) {
                primeNumbers.add(num);
            }
        }
        
        // 순열을 구하기 위한 재귀 호출
        for (int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), primeNumbers);
        }
    }
    
    // 주어진 정수가 소수인지 판별하는 메서드
    private boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        
        // 2와 3으로 나누어 떨어지는 경우 소수가 아님
        if (num % 2 == 0 || num % 3 == 0) return false;
        
        // i의 제곱이 주어진 정수보다 작거나 같은 동안, 주어진 정수를 i로 나누어 떨어지는지 확인
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) return false;
        }
        
        // 위 조건을 모두 통과하면 소수로 판별
        return true;
    }
}