프로그래머스 - 소수 찾기

2단계

문제 설명

• 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

• 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

import java.util.*;
import java.util.stream.*;

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

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

        int[] data = Stream.of(numbers.split("")).mapToInt(Integer::valueOf).toArray();
        int[] output = new int[data.length];
        boolean[] flags = new boolean[data.length];

        for (int i = 1; i <= numbers.length(); i++)
            perm(0, i, data, output, flags);

        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            int target = iterator.next();
            if (target == 2)
                answer++;
            if (target % 2 != 0 && isPrime(target))
                answer++;
        }

        return answer;
    }
    
    private boolean isPrime(int n) {
        if (n == 0 || n == 1)
            return false;
        
        for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
            if (n % i == 0)
                return false;
        }
        
        return true;
    }

    private void perm(int depth, int count, int[] data, int[] output, boolean[] flags) {
        if (depth == count) {
            String temp = "";
            for (int i = 0; i < count; i++)
                    temp += output[i];
            set.add(Integer.valueOf(temp));
        }

        for (int i = 0; i < data.length; i++) {
            if (!flags[i]) {
                flags[i] = true;
                output[depth] = data[i];
                perm(depth + 1, count, data, output, flags);
                flags[i] = false;   
            }
        }
    }
}

순열을 이용하여 풀 수 있는 문제였습니다. 큰 어려움은 없었으나 순열과 조합의 경우 자바는 라이브러리가 기본 제공되는 것이 없어 매번 구현에 애를 먹네요... ㅜㅜ 소수 판별의 경우도 아직 저만의 것으로 확립하지 못한 것 같습니다. 수학적 지식을 정리해야할 필요를 느꼈습니다...