참고
문제해설
문제 로직고민
NOTE
•
문자열을 char[] 요소로 분해한뒤, 모든 경우를 진행한다
◦
문제 유형을 알기때문에 브루트포스가 해결책인걸 알지만, 문제를 보았을때 브루트포스가 해답이 되는지 판단하는 역량이 필요하다 생각든다.
◦
현재 제한사항으로 문자열 길이는 7이하이며, 숫자의 경우 10가지 경우 기준으로 했을때, 1천만으로 허용되는 범위라 판단한다.
•
소수의 경우 에라토네스체를 사용한다.
◦
숫자의 범위는 길이가 7이므로, 1000000이하까지의 소수를 구한다.
작성코드
NOTE
import java.util.*;
class Solution {
int answer;
boolean[] visited;
boolean[] prime;
HashSet<Integer> set;
String number;
public int solution(String numbers) {
visited = new boolean[numbers.length()];
prime = createPrime();
set = new HashSet();
number = numbers;
dfs("");
return set.size();
}
public boolean[] createPrime(){
boolean[] pr = new boolean[10000000];
pr[0] = true;
pr[1] = true;
for(int i = 2; i<pr.length; i++){
if(!pr[i]){
for(int j=i+i; j<pr.length; j += i){
pr[j] = true;
}
}
}
return pr;
}
public void dfs(String num){
if(!num.equals("") && !prime[Integer.parseInt(num)]) set.add(Integer.parseInt(num));
for(int i =0; i<number.length(); i++){
if(!visited[i]){
visited[i] = true;
dfs(num + number.charAt(i));
visited[i] = false;
}
}
}
}
Java
복사
다른사람 풀이
NOTE
import java.util.HashSet;
class Solution {
public int solution(String numbers) {
HashSet<Integer> set = new HashSet<>();
permutation("", numbers, set);
int count = 0;
while(set.iterator().hasNext()){
int a = set.iterator().next();
set.remove(a);
if(a==2) count++;
if(a%2!=0 && isPrime(a)){
count++;
}
}
return count;
}
public boolean isPrime(int n){
if(n==0 || n==1) return false;
for(int i=3; i<=(int)Math.sqrt(n); i+=2){
if(n%i==0) return false;
}
return true;
}
public void permutation(String prefix, String str, HashSet<Integer> set) {
int n = str.length();
//if (n == 0) System.out.println(prefix);
if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
}
}
Java
복사
가장 평가가 좋은 코드
•
소수판별의 경우 루트값까지만 확인하는 isPrime()을 사용함
•
이외에는 동일