[BOJ 3671] 산업 스파이의 편지(Java, 소수 구하기, DFS)

https://www.acmicpc.net/problem/3671

3671번: 산업 스파이의 편지

 

1. 주어진 문자열을 순열로 나열해서 소수인지 판단하기

 

 

 

2. 소수가 맞다면, 중복 제거를 위한 Set 자료구조에 넣기

 

 

 

3. Set의 Size 출력하기

 

---

 

* 소수인지 판단하는 가장 효율적인 알고리즘

 

 

 

판단하는 수의 루트값을 이용해서 for문을 작성하면 된다. 루트값까지만 사용하면, 소수인지 아닌지 판별할 수 있다.

 

 

 

왜냐하면, 루트값 이후의 값들은 모두 루트값 이전 약수들을 이용해서 만들 수 있기 때문이다.

 

 

---

 

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static Scanner sc;
    static int c, n;
    static boolean[] check;
    static HashSet<Integer> hSet;
    static String str; 
 
    public static void main (String[] args) throws java.lang.Exception
    {
        sc = new Scanner(System.in);
        check = new boolean[7];
        hSet = new HashSet<Integer>();
        
        c = sc.nextInt();
        for(int i = 1; i <= c; i++){
            str = sc.next();
            hSet.clear();
            for(int j = 0; j < str.length(); j++) check[j] = false;
            
            dfs("");
            System.out.println(hSet.size());
        }
    }
    
    public static void dfs(String s){
        for(int i = 0; i < str.length(); i++){
            if(check[i] == false){
                String tmp = s + str.charAt(i);
                int num = Integer.parseInt(tmp);
                
                check[i] = true;
                if(isPrime(num)) hSet.add(num);
                dfs(tmp);
                check[i] = false;
            }
        }
    }
    
    public static boolean isPrime(int num){
        if(num == 1 || num == 0) return false;
        
        for(int i = 2; i * i <= num; i++){
            if(num % i == 0) return false;
        }
        
        return true;
    }
}