[프로그래머스] 소수 찾기 42839 (JAVA)

풀이 방식

1. 주어진 숫자를 담는 ArrayList와 순열 조합을 담을 HashSet 생성
2. 정렬된 리스트에서 숫자를 돌아가면서 하나씩 뽑은 후 순열 메소드 호출
3. 순열 메소드에서는 재귀 호출을 통해 순열 조합을 생성
4. 만들어진 순열 조합에서 하나씩 돌아가며 소수 검사 메소드 호출
5. 소수 검사 메소드 결과에 따라 정답 카운트

포인트

순열

DFS 방식으로 순열 만들기

구현

public class NUM42839 {
    public static void main(String[] args) {
        String numbers = "1753";
        System.out.println(solution(numbers));
    }

    public static int solution(String numbers) {
        int answer = 0;
        
        ArrayList<String> numberList = new ArrayList<>(Arrays.asList(numbers.split("")));
        HashSet<Integer> permutations = new HashSet<>();

        for(int i = 0; i < numberList.size(); i++) {
            Collections.sort(numberList);
            String current = numberList.remove(i);
            // System.out.println("numberList.remove = " + current);
            addPermutation(numberList, permutations, current);
            // System.out.println("numberList.add = " + current);
            numberList.add(current);
        }

        for(Integer p : permutations) { if(isPrime(p)) { answer++; } }
        return answer;
    }

    public static void addPermutation(ArrayList<String> numberList, HashSet<Integer> permutations, String current) {
        // System.out.println("permutations.add = " + current);
        permutations.add(Integer.parseInt(current));
        for(int i = 0; i < numberList.size(); i++) {
            String next = numberList.remove(0);
            // System.out.println("numberList.remove = " + next);
            addPermutation(numberList, permutations, current + next);
            numberList.add(next);
            // System.out.println("numberList.add = " + next);
        }
    }

    public static boolean isPrime(int number) {
        if(number <= 1 || (number != 2 && number % 2 == 0)) { return false; }
        for(int i = 3; i <= Math.sqrt(number); i+=2) { if(number % i == 0) { return false; } }
        return true;
    }
}

---

*다른 분들의 코드를 참고하여 작성했습니다