프로그래머스 소수 찾기 풀이.

문제 링크
현재 사실 문제를 풀기보다는
알고리즘 공부를 하고 있는 게 메인이다보니,

좀 복잡하고 불필요한 코드가 많지만, 한 번 해봤다.

3가지 흐름으로 가는데,

주어진 문자열로 만들 수 있는 순열
(백트랙킹)

주어진 배열 중에 가장 큰 수 까지의 소수 배열.

그래서 그 소수와 같은지 판별.

import java.util.*;

public class Main {
    public static boolean[] visited;
    public static Set<Integer> set;
    public static void main(String[] args) {
        String input;
        Scanner scan = new Scanner(System.in);
        input = scan.next();
        visited = new boolean[input.length()];
        set = new HashSet<>();
        backTracking(0, input, "");
        Object[] array = set.toArray();
        Arrays.sort(array);
        System.out.println("num Sets");
        for(int i = 0; i< array.length; i++){
            System.out.print(array[i]+", ");
            if(i % 10 == 9 ) System.out.println();
        }
        System.out.println();
        System.out.println();
        System.out.print("Prime Numbers");
        ArrayList<Integer> prime = FindPrimeNums((int)array[array.length-1]);
        for(int i = 0 ; i < prime.size(); i++){
            System.out.print(prime.get(i) + ", ");
            if(i % 10 == 9 ) System.out.println();
        }
        System.out.println();
        System.out.println();
        System.out.println("the num of Primes : " +check(array, prime));
    }
    public static void backTracking(int depth, String inputNum, String current){
        if(depth == inputNum.length()) return;

        for(int i = 0 ; i<inputNum.length(); i++){
            if(!visited[i]){
                visited[i]= true;
                String num = current+inputNum.charAt(i);
                set.add(Integer.parseInt(num));

                backTracking(depth+1, inputNum, num);
                visited[i] = false;
            }
        }
    }
    public static ArrayList<Integer> FindPrimeNums(int maxNum){
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Boolean> isCheck = new ArrayList<>(Arrays.asList(true));
        Boolean[] isChecked = new Boolean[maxNum];

        for(int i = 1 ; i <= maxNum; i++)
        {
            isChecked[i-1] = false;
        }
        for(int i = 2 ; i * i <= maxNum+1; i++)
        {
            if(isChecked[i-2]) continue;
            for(int j = i*i ; j<=maxNum+1 ; j+=i)
            {
                isChecked[j-2] = true;
            }
        }
        System.out.println();
        for(int i = 0; i < isChecked.length; i++)
        {
            if(!isChecked[i]){
                list.add(i+2);
            }
        }
        return list;
    }
    public static int check(Object[] numbers, ArrayList<Integer> primes){
        int num = 0;
        for(int i = 0; i<numbers.length;i++){
            for(int j = 0; j<primes.size(); j++)
            {
                if(primes.get(j) == numbers[i]) num++;
            }
        }
        return num;
    }

}

이런 코드로 적었는데,
정렬은 지금 당장 머리에 안 떠올라서 구현하지 않았다.
백패킹 알고리즘 같은 경우는 인터넷에서 검색후 따라쳤기에 완벽히 이해하지는 못했다.