이번에 풀어본 문제는
프로그래머스 소수 찾기
입니다.

📕 문제 링크

❗️코드

import java.util.HashSet;
import java.util.Set;
class Solution {
    static int SIZE;
    static char [] charArray;
    static Set<Integer> set;
    static boolean [] isNotPrime;
    static int MAX_VALUE = 10_000_000;
    public int solution(String numbers) {
        int answer = 0;
        SIZE = numbers.length();
        charArray = numbers.toCharArray();
        set = new HashSet<>();
        // 만들 수 있는 수
        makeNumbers("", new boolean[SIZE], 0);

        // 소수 모두구함 최댓값 9,999,999
        isNotPrime = new boolean[MAX_VALUE];
        isNotPrime[0] = true;
        isNotPrime[1] = true;
        makePrimes();
        for (int n: set) {
            if (!isNotPrime[n]) answer++;
        }
        return answer;
    }
    static void makeNumbers(String number, boolean [] isVisited, int count) {
        if (count == SIZE) {
            if (number.length() > 0) {
                set.add(Integer.parseInt(number));
            }
            return;
        }

        for (int i = 0; i < SIZE; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                makeNumbers(number + charArray[i], isVisited, count + 1);
                isVisited[i] = false;
                makeNumbers(number, isVisited, count + 1);
            }
        }
    }
    static void makePrimes() {
        for (int i = 2; i*i < MAX_VALUE; i++) {
            if (!isNotPrime[i]) {
                for (int j = i * i; j < MAX_VALUE; j += i) {
                    isNotPrime[j] = true;
                }
            }
        }
    }
}

📝 풀이

숫자로만 이루어진 주어진 문자열에서, 일의자리로 각 숫자를 나눕니다. 이후, 해당 숫자로 만들 수 있는 모든 수 중에서 소수인 것의 개수를 구하는 문제입니다.
먼저 주어진 문자열에 속한 숫자로 만들 수 있는 모든 수를 순열을 통해 set에 담아줍니다. 문자열내에 중복 숫자가 존재한다면 중복 카운트가 들어갈 수 있기 때문에 set을 활용해줍니다.
이후에는 소수값만 체크해주면 해결할 수 있습니다.