소수 찾기(문제21)

import java.util.*;

class Solution {
    private static Set<Integer> sosuSet = new HashSet<>();
    private static StringBuilder sb = new StringBuilder();
    private static String num;
    private static boolean[] visited;
    public int solution(String numbers) {
        num = numbers;
        visited = new boolean[num.length()];
        solve(0);
        return sosuSet.size();
    }
    
    private static void solve(int depth){
        if(sb.length() != 0 && isSosu(Integer.parseInt(sb.toString()))) sosuSet.add(Integer.parseInt(sb.toString()));
        
        if(depth == num.length()){
            return;
        }
        
        for(int i=0 ; i<num.length() ; i++){
            if(visited[i]) continue;
            visited[i] = true;
            sb.append(num.charAt(i));
            
            solve(depth+1);
            
            visited[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }
    
    private static boolean isSosu(int source){
        if(source <= 1) return false;
        for(int i=2 ; i<source ; i++){
            if(source % i == 0) return false;
        }
        //System.out.println(source);
        return true;
    }
}

재미니 도움

import java.util.*;

class Solution {
    // 1. static 필드 제거
    private HashSet<Integer> sosuSet;
    private boolean[] visited;
    private char[] nums; // String 대신 char 배열로 바꾸면 매번 charAt() 호출을 안해도 되어 약간 더 효율적입니다.

    public int solution(String numbers) {
        // 2. solution 메서드 내에서 변수들을 초기화
        sosuSet = new HashSet<>();
        nums = numbers.toCharArray();
        visited = new boolean[nums.length];
        
        // 빈 문자열부터 시작하여 모든 숫자 조합을 탐색
        dfs(""); 
        
        return sosuSet.size();
    }
    
    // 3. 재귀 함수(DFS)는 필요한 데이터를 파라미터로 받거나, 클래스 멤버 변수에 접근
    private void dfs(String currentNum) {
        // 현재 만들어진 숫자가 빈 문자열이 아니라면 소수인지 판별
        if (!currentNum.isEmpty()) {
            int numInt = Integer.parseInt(currentNum);
            if (isSosu(numInt)) {
                sosuSet.add(numInt);
            }
        }
        
        // 모든 숫자 조각을 한 번씩 사용해보며 순열 생성
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(currentNum + nums[i]); // 다음 숫자를 붙여서 재귀 호출
                visited[i] = false; // 재귀가 끝나면 방문 표시 해제 (백트래킹)
            }
        }
    }
    
    // 4. 개선된 소수 판별 메서드 (static 제거)
    private boolean isSosu(int source) {
        if (source <= 1) return false;
        for (int i = 2; i * i <= source; i++) {
            if (source % i == 0) return false;
        }
        return true;
    }
}