소수 찾기

문제

---

문제 풀이

입력되는 문자열에 따라 길이가 1 ~ 문자열 길이까지안에서 가능한 모든 숫자를 만들어서 중복은 빼고 나온 수들 중에, 소수를 찾아야 하는 문제이다. 

 

순열로 만들어지는 숫자들 규칙으로 visited 불리안 배열을 하고 방문할 때는 방문여부를 true로 변환하고  추가되는 문자에 문자를 추가한다. 

 

나올 때는 문자를 제거하고 방문여부를 false로 변경하면 순열로 나올 수 있는 모든 경우의 수를 체크 할 수있다. 

 

그리고 각 길이마다 순열을 체크해야하기 때문에 solution에서 호출 하면서 최대 길이 값도 for문으로 같이 지정을 하여 넘겨주었음. 

---

나의 답안

static ArrayList<Integer> all = new ArrayList<>();
static boolean[] visited = new boolean[7];

public static int solution(String numbers) {
    int answer = 0;

    String[] split = numbers.split("");

    for (int i = 1; i <= split.length; i++) {
        dfs(split, visited, "", i);
    }

    for (int i = 0; i < all.size(); i++) {
        int target = all.get(i);
        if (target < 2) continue;

        boolean flag = false;
        for (int j = 2; j <= Math.sqrt(target) ; j++) {
            if (target % j == 0) flag = true;
        }

        if (!flag) answer++;
    }
    return answer;
}

private static void dfs(String[] split, boolean[] visited, String num, int len) {
    if (num.length() == len) {
        int a = Integer.parseInt(num);
        if (!all.contains(a)) {
            all.add(a);
        }
    }
    for (int i = 0; i < split.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            num += split[i];
            dfs(split, visited, num, len);
            visited[i] = false;
            num = num.substring(0, num.length()-1);
        }
    }
}