[Algorithm][Programmers] 소수 찾기 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

입출력 예시

풀이

모든 경우의 수를 확인해야 한다고 생각하여 순열을 사용해서 풀이하였습니다.

나온 수들을 모두 HashSet에 담고 마지막에 isPrime() 함수를 통해 소수를 판별해주었습니다.

코드

import java.util.*;
class Solution {
    HashSet<Integer> numSet = new HashSet<>();
    public int solution(String numbers) {   
        boolean[] visited = new boolean[numbers.length()];
        permutation(0, numbers, "", visited);        
        int answer = 0;
        for(int num : numSet) {
            if(isPrime(num)) answer++;            
        }
        
        return answer;
    }
    public void permutation(int cnt, String numbers, String temp, boolean[] visited) {
        if(!temp.equals("")) {        
            numSet.add(Integer.parseInt(temp));            
        }
        for(int index = 0; index < numbers.length(); index++) {
            if(!visited[index]) {         
                String base = temp + String.valueOf(numbers.charAt(index) - '0');
                visited[index] = true;
                permutation(cnt + 1, numbers, base, visited);            
                visited[index] = false;
            }
        }
    }
    public boolean isPrime(int num) {
        if(num == 0 || num == 1) return false;
        int check = (int) Math.sqrt(num);
        for(int index = 2; index <= check; index++) {
            if(num % index == 0) return false;
        }
        return true;
    }
}

제한 사항