프로그래머스 - 소수 찾기(Java, 자바)

문제 링크

문제 설명

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

*11과 011은 같은 숫자로 취급합니다.

---

문제 풀이 방법

1. 주어진 문자열을 toCharArray()을 사용하여 각 배열에 숫자 한개씩 넣는다.
2. DFS 탐색 방법으로 주어진 카드로 만들 수 있는 모든 숫자 조합을 만든다.
3. 탐색을 완료 했을 때 해당 숫자가 소수라면 HashSet 에 넣는다.
4. 이때 HashSet 을 사용한 이유는 만들어진 숫자의 중복 방지를 위함이다.
5. 최종적으로 HashSet 의 크기가 정답이 된다.

---

전체 코드

import java.util.*;

class Solution {
    public static char[] card;
    public static boolean[] visited;
    public static HashSet<Integer> set;
    public int solution(String numbers) {
        
        visited = new boolean[numbers.length()];
        card = numbers.toCharArray();
        set = new HashSet<>();
        dfs(0, "");
        return set.size();
    }
    
    public static void dfs(int depth, String num){
        if(depth == visited.length){
            if(num.equals("")){
                return;
            }
            int temp = Integer.parseInt(num);
            if(isPrime(temp)){
                set.add(temp);
            }
            return;
        }

        for (int i = 0; i < card.length; i++) {
            if(!visited[i]){
                visited[i] = true;
                dfs(depth + 1, num + card[i]);
                visited[i] = false;
                dfs(depth + 1, num);
            }
        }
    }
    
    public static boolean isPrime(int n){
        if(n <= 1) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}