[JAVA 문제 풀이] 356. 소수 찾기

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(String numbers) {
        String[] arr = numbers.split(""); // 문자열을 배열로 변환
        Set<Integer> arr2 = getAllMixture(arr); // 배열의 모든 조합을 반환
        int answer = 0;

        // 소수 판별
        for (Integer i : arr2) {
            if (isPrime(i)) {
                answer++;
            }
        }

        return answer;
    }

    // 소수 확인 메서드
    private boolean isPrime(int i) {
        if (i < 2)
            return false;

        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0)
                return false;
        }

        return true;
    }

    // 배열의 모든 조합을 반환하는 메서드
    public Set<Integer> getAllMixture(String[] arr) {
        Set<Integer> result = new HashSet<>(); // 결과를 저장할 set 생성
        boolean[] visited = new boolean[arr.length]; // 각 문자의 사용 여부를 체크하는 배열

        backtrack(arr, "", visited, result);

        return result;
    }

    // 배열의 모든 조합을 생성하는 재귀메서드
    private void backtrack(String[] arr, String current, boolean[] visited, Set<Integer> result) {
        if (current.length() > 0) { // 1개 이상 선택된 경우마다 저장
            result.add(Integer.parseInt(current));
        }

        if (current.length() == arr.length) {
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) { // 아직 사용하지 않은 문자일 경우
                visited[i] = true; // 해당 문자를 사용 처리
                backtrack(arr, current + arr[i], visited, result); // 다음 문자 선택을 위해 재귀 호출
                visited[i] = false; // 재귀가 끝나면 미사용 처리
            }
        }
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        // 모든 순열 조합을 만들고, 중복 없이 set에 저장
        permutation("", numbers, set);

        int count = 0;

        // set에 저장된 숫자를 하나씩 검사
        while (set.iterator().hasNext()) {
            int a = set.iterator().next(); // set에서 하나 꺼내기
            set.remove(a); // 중복 제거를 위해 즉시 삭제

            if (a == 2)
                count++; // 2는 예외적으로 짝수이지만 소수
            // 홀수이면서 소수인지 검사
            if (a % 2 != 0 && isPrime(a)) {
                count++;
            }
        }

        return count;
    }

    // 소수 판별 메서드
    public boolean isPrime(int n) {
        if (n == 0 || n == 1)
            return false; // 0, 1은 소수 아님
        // 홀수만 체크 (2는 예외 처리됨)
        for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
            if (n % i == 0)
                return false; // 나누어 떨어지면 소수 아님
        }
        return true;
    }

    // 가능한 모든 순열 조합을 만들어 set에 저장
    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);
        }
    }
}

Backtracking(백트래킹) - stupefyee

기술정리

https://stupefyee.inblog.io/backtracking%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-60939?traffic_type=internal