프로그래머스 소수 찾기 JAVA (feat. 에라토스테네스의 체)

해당 문제는 완전 탐색이어서 permutation을 통해서 모든 순열을 찾고(단, 중복은 제거해야 하므로 Set으로 저장한다.) 그 순열이 소수인지 아닌지 여부를 판단하면 되는 쉬운 문제이다.
하지만 기본적으로 모든 순열을 구하는 과정이 nPn + nPn-1 + ... + nP1 이므로 최대의 문자열의 길이가 7이기 때문에 7! + 6!..이고 매 숫자마다 단순히 반복문을 이용해서 소수 여부를 판단하면 시간이 너무 많이 소요된다.

따라서 이러한 시간을 줄이기 위해 소수 여부를 사전에 판단하는 에라토스테네스의 체를 이용한다.
코드는 https://firework-ham.tistory.com/8 의 블로그를 참조하였다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    Set<Integer> lists = new HashSet<>();

    public Set<Integer> permute(String numbers) {
        char[] nums = numbers.toCharArray();
        for(int i = 1; i<=numbers.length();i++) {
            permutation(nums, new char[i], new boolean[nums.length], 0, nums.length, i);
        }
        return lists;
    }

    public void permutation(char[] nums, char[] outputs, boolean[] visited, int depth, int n, int r) {
        if (depth == r) {
            StringBuilder sb = new StringBuilder();
            for (char singleNum : outputs) {
                sb.append(singleNum);
            }
            insertToList(sb.toString());
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                outputs[depth] = nums[i];
                permutation(nums, outputs, visited, depth+1, n, r);
                visited[i] = false;
            }
        }
    }

    public void insertToList(String outputs) {
        lists.add(Integer.parseInt(outputs));
    }

    public int solution(String numbers) {
        int answer = 0;
        boolean[] prime = new boolean[10000001];
        prime[0] = prime[1] = true;

        for(int i=2; i*i<=prime.length-1; i++){
            // prime[i]가 소수라면
            if(!prime[i]){
                for(int j=i*i; j<=prime.length-1; j+=i) prime[j]=true;
            }
        }

        permute(numbers);

        for(int item : lists) {
            if(!prime[item]){
                answer++;
            }
        }

        return answer;
    }
}