99클럽 코테 스터디 23일차 TIL - 프로그래머스[소수찾기]

문제 풀이

오늘의 문제 - 프로그래머스.소수찾기

나의 풀이

import java.util.*;

class Solution {
    public int solution(String numbers) {
        // 숫자 조합을 저장할 Set 생성(중복 제거)
        Set<Integer> numSet = new HashSet<>();
        
        // 빈 prefix로 시작하여 numbers로 만들 수 있는 모든 숫자 조합 생성
        permutation("", numbers, numSet);
        
        int cnt = 0; // 소수 개수 세는 변수
        // numSet에 저장된 모든 숫자에 대해 소수인지 확인
        for(int num : numSet) {
            // 소수 판별
            if(isPrime(num)) {
                cnt++; // 소수이면 카운트 증가
            }
        }
        
        return cnt;
    }
    
    private static void permutation(String prefix, String str, Set<Integer> numSet) {
        int n = str.length(); // 남은 숫자 문자열의 길이를 n에 저장
        
        if(!prefix.equals("")) {
            numSet.add(Integer.parseInt(prefix));
        }
        
        // 남은 문자열 순회 => 자기 자신을 다시 호출
        for(int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), numSet);
        }
    }
    
    // 소수 판별 함수
    private static boolean isPrime(int num) {
        if(num <= 1) return false;
        for(int i = 2; i * i <= num; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}