[전체 코드]

import java.util.*;

class Solution {
    static Set<Integer> set = new HashSet<>();
    static boolean[] visited;
    static String numbers;

    public boolean isPrime(int num) {
        if (num < 2) return false;
        
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public void backTrack(String str) {
        if (!str.equals("")) {
            set.add(Integer.parseInt(str));
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                backTrack(str + numbers.charAt(i));
                visited[i] = false; // backTrack
            }
        }
    }

    public int solution(String numbers) {
        this.numbers = numbers;
        visited = new boolean[numbers.length()];

        backTrack(""); // numbers을 활용하여 순열 생성.
        
        int answer = 0;

        for (int num : set) {
            if (isPrime(num)) {
                answer++;
            }
        }

        return answer;
    }
}

[문제 풀이 설명]

우선 문제를 간략히 설명하자면, 예를 들어 "17"이라는 문자열을 입력 받으면 [1, 7, 17, 71] 이라는 소수를 구하고 해당 소수의 개수를 반환해야 하는 문제이다.

처음에는 minValue = 1, maxValue = 71을 구하고 총 71번의 for문을 돌리며 소수인지 판별하는 로직으로 생각했으나 엄청난 시간 낭비인 것 같다는 생각이 들었다. 그래서 해당 문자열로 구성된 순열을 구하자고 생각했고, 순열 구하기 -> 완전 탐색 -> 백트래킹 이 떠올라 백트래킹을 활용하여 문제를 풀었다.

🔎 여기서 순열이란?

: 순서가 중요한 배열을 뜻한다. 71과 17은 엄연히 다른 숫자이므로 순열로 풀어야 한다.

numbers의 길이 만큼 for문을 돌리고 방문 처리를 하며, 빈 문자열이 아니면 set에 add 하는 식으로 풀었다.

[어려웠던 점]

우선 처음에 문제를 보자마자 순열을 떠올렸어야 했는데 웬 71번의 반복문 돌릴 생각을 먼저 했다. . .
그리고 백트래킹 코드를 너무 오랜만에 짜서 약간 어려웠다.

[느낀점]

그래도 예전에 백트래킹 관련 문제를 많이 풀어놔서, 순열! 하면 바로 백트래킹이 떠올라서 다행이라고 생각한다.