[프로그래머스] 소수 찾기 (java)

🔗 문제링크

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

👩🏻‍💻 코드

import java.io.*;
import java.util.HashSet;
import java.util.Set;

class Solution {
    static String origin;
    static boolean[] visited = new boolean[7];
    static Set<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        origin = numbers;
        dfs("", 0);
        return set.size();
    }
    
    public static 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 static void dfs(String str, int cnt) {
        if (cnt == origin.length()) {
            if (!str.equals("") && isPrime(Integer.parseInt(str))) {
                set.add(Integer.parseInt(str));
            }
        }

        for (int i = 0; i < origin.length(); i++) {
            if (visited[i]) continue;

            visited[i] = true;
            dfs(str + origin.charAt(i), cnt + 1);
            dfs(str, cnt + 1);
            visited[i] = false;
        }
    }
}

📝 정리

dfs를 재귀호출할 때
(1) 현재의 문자를 붙여서 호출
(2) 현재의 문자를 붙이지 않고 호출
하면서 모든 경우의 수를 만들어본 후, 소수인지 판별했다.