[프로그래머스] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

코드

import java.util.HashSet;
import java.util.Set;

public class Solution {
    static boolean[] visited;
    static char[] charArray;
    static Set<Integer> result = new HashSet<>();

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

        charArray = numbers.toCharArray();
        visited = new boolean[charArray.length];

        for (int i = 0; i < charArray.length; i++) {
            dfs(0, i + 1, "");
        }

        for (int num : result) {
            if (isPrime(num)) {
                answer++;
            }
        }

        return answer;
    }

    static private void dfs(int depth, int digits, String num) {
        // N자리수 숫자가 완성되면 소수 판별
        if (depth == digits) {
            result.add(Integer.parseInt(num));
            return;
        }
        
        for (int i = 0; i < charArray.length; i++) {
            // 정수의 첫째 자리가 0이면 생략
            if (depth == 0 && charArray[i] == '0') {
                continue;
            }

            if (!visited[i]) {
                visited[i] = true;
                dfs(depth + 1, digits, num + charArray[i]);
                visited[i] = false;
            }
        }
    }

    // 소수 판별 함수
    static public boolean isPrime(int number) {
        // 1보다 작거나 같은 경우 소수가 아님
        if (number <= 1) {
            return false;
        }
        // 2와 3은 소수
        if (number == 2 || number == 3) {
            return true;
        }
        // 짝수이거나 3으로 나누어 떨어지면 소수가 아님
        if (number % 2 == 0 || number % 3 == 0) {
            return false;
        }
        // 5부터 루트 number까지 홀수에 대해 나눠보며 검사
        for (int i = 5; i * i <= number; i += 6) {
            if (number % i == 0 || number % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

풀이

숫자 카드로 만들 수 있는 모든 경우의 수를 찾기 위해 DFS를, 결과의 중복 제거를 위해 Set 자료형을 사용했다.

나 같은 경우 자릿수 별로 숫자를 구했다. 예를 들어 입력으로 "317"이 들어왔을 때, 한 자리 숫자만 따로 구하고, 두 자리 숫자, 세 자리 숫자를 각각 구하도록 했다.

마지막에는 Set를 순회하면서 소수인 경우에만 정답에 추가되도록 했다. 원래는 재귀의 종료 조건에 다다를 때마다 소수 검사를 했었는데, 성능적으로는 크게 차이가 없었다.