소수 찾기

import java.util.*;
class Solution {
    static Set<Integer> set = new HashSet<Integer>();
    
    public void DFS(ArrayList<String> list, ArrayList<String> res, int i, int n) {
        // 마지막 배열을 입력했을 때
        if (i == 0) {
            return;
        }
 
        // 모든 경우의 수를 구하여 set에 저장
        for (int j = 0; j < n; j++) {
            res.add(list.remove(j));
            String[] s = res.toArray(new String[res.size()]);
            set.add(Integer.parseInt(String.join("", s)));
            DFS(list, res, i - 1, n - 1);
            list.add(j, res.remove(res.size() - 1));
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;
        String[] arr = numbers.split(""); // 숫자 분할
        ArrayList<String> list = new ArrayList<String>(Arrays.asList(arr));
        ArrayList<String> res = new ArrayList<String>();
        DFS(list, res, list.size(), list.size());
 
        // 소수 구하기
        Iterator<Integer> iterSet = set.iterator();
        while (iterSet.hasNext()) {
            int i;
            int n = iterSet.next();
            int sqrt = (int) Math.sqrt(n);
 
            if (n > 1) {
                for (i = 2; i <= sqrt; i++) {
                    if (n % i == 0)
                        break;
                }
                if (i == sqrt + 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

주어진 수를 분할하여 나올 수 있는 모든 수를 구한 후 소수가 몇 개인지 판별하는 문제이다.

기존에 알게 된 ArrayList를 이용한 모든 경우의 수를 구하는 방법을 이용하였다.

새로운 방법으로 StringBuilder를 이용한 DFS를 이용하려 했지만 변수의 값이 임의로 변경되어 실패했다.

 

다른 사람의 풀이 중 훨씬 좋은 방법을 발견하였다.

import java.util.HashSet;
 
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while (set.iterator().hasNext()) {
            int a = set.iterator().next();
            set.remove(a);
            if (a == 2)
                count++;
            if (a % 2 != 0 && isPrime(a)) {
                count++;
            }
        }
        return count;
    }
 
    public 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;
    }
 
    public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        if (!prefix.equals(""))
            set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), set);
    }
}

permutation 함수를 보면 반복문을 통해 문자를 고르고, 고른 문자를 제거하는 방법으로 substring을 이용하였다.

또한 isPrime에 들어가기전 13번 라인의 a % 2를 통해 짝수를 배제함으로써 i = 3부터 i += 2로 빠르게 탐색이 가능하게 하였다.

단, 이 방법을 사용하기 위해서는 함수를 분리하여 반환 값을 통해 구분하거나, 특정 변수를 추가로 생성해야 한다.