알고리즘/백준
[BOJ 3671] 산업 스파이의 편지(Java, 소수 구하기, DFS)
I L G N O Y
2020. 8. 8. 11:11
https://www.acmicpc.net/problem/3671
3671번: 산업 스파이의 편지
문제 안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요. 저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매��
www.acmicpc.net
1. 주어진 문자열을 순열로 나열해서 소수인지 판단하기
2. 소수가 맞다면, 중복 제거를 위한 Set 자료구조에 넣기
3. Set의 Size 출력하기
* 소수인지 판단하는 가장 효율적인 알고리즘
판단하는 수의 루트값을 이용해서 for문을 작성하면 된다. 루트값까지만 사용하면, 소수인지 아닌지 판별할 수 있다.
왜냐하면, 루트값 이후의 값들은 모두 루트값 이전 약수들을 이용해서 만들 수 있기 때문이다.
해설코드(Java).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
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;
}
}
|