[프로그래머스 알고리즘 고득점 Kit][완전탐색][Java] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=java

프로그래머스

프로그래머스 소수 찾기 풀이

이 문제는 주어진 숫자 문자열로 만들 수 있는 모든 숫자 중 소수의 개수를 구하는 문제다.

각 숫자 조각을 한 번씩만 사용할 수 있으므로 visited 배열을 사용해 이미 사용한 숫자인지 체크했다.
DFS/백트래킹으로 숫자를 하나씩 붙이며 만들 수 있는 모든 순열을 생성했다.

예를 들어 "17"이라면 1, 7, 17, 71을 만들 수 있다.

중복 숫자가 생길 수 있기 때문에 생성한 숫자는 Set에 저장했다.
예를 들어 "117"에서는 위치가 다른 1을 사용해도 같은 숫자 117이 만들어질 수 있으므로 중복 제거가 필요하다.

모든 숫자를 만든 뒤에는 Set을 순회하면서 각 숫자가 소수인지 판별했다.
소수 판별은 2부터 i * i <= n까지만 나누어보면 된다.
약수는 짝으로 존재하기 때문에 제곱근까지만 확인해도 충분하다.

정리하면, 이 문제는 백트래킹으로 모든 숫자 순열을 만들고, Set으로 중복 제거 후 소수를 판별하는 완전탐색 문제다.

정답 코드

import java.util.*;

class Solution {

    int len;
    Set<Integer> set;
    boolean[] visited;
    String numbers;

    public int solution(String numbers) {
        this.len = numbers.length();
        set = new HashSet<>();
        this.visited = new boolean[len];
        this.numbers = numbers;
        
        dfs(new StringBuilder());


        int ans = 0;
        for(int n : set) {
            if(isPrime(n)) ans++;
        }

        return ans;
    }
    private void dfs(StringBuilder current) {
        if(current.length() > 0) {
            this.set.add(Integer.parseInt(current.toString()));
        }

        for(int i=0; i<len; i++) {
            if(visited[i]) continue;
            
            visited[i] = true;
            current.append(numbers.charAt(i));

            dfs(current);
            
            current.deleteCharAt(current.length() - 1);
            visited[i] = false;
        }
    }
    private boolean isPrime(int n) {
        if(n < 2) return false;
        
        for(int i=2; i*i <= n; i++) {
            if(n % i == 0) return false;
        }
        
        return true;
    }
}