🕐 풀이시간 : 1시간 30분
💡 해결 아이디어
혼자 열심히 끙끙대면서 1시간 30분동안 풀어서 정답을 구했다!
20분정도 계속 종이에 어떻게 풀 지 분석하면서 "아..이게 안되겠는데 그냥 풀이 참고를 하는 게 나을까" 싶은 생각이 들었지만 이 전에 풀이한 문제에서 풀이를 쉽게 본 게 후회가 남아서 계속 풀어봤다!
숫자들을 조합하자
가장 처음에 고민되는 부분이 예시로 1,7이라면 1, 7, 17, 71 이렇게 나올텐데 이러한 숫자들을 어떻게 뽑아낼까 라는 부분이었다.
문자를 막 조합해서 만들어야할 거 같은데 직접 써보면서 만들어볼수록 백준에서 N과M풀었던 아이디를 이용하면 어떨까 라는 생각이 들었다.
이 문제에서는 1,2,3,4를 가지고 조합해서 1234 1243 1324 1342..등과 같이 숫자들을 만드는 문젠데 이 문제에 접목시킨다면 쉽게 풀이가 가능할 것 같았다! 하지만 여기서 다른 부분은 이 문제는 한 자리 숫자부터 n길이 전부를 list에 넣어두어야 하고 중복이 발생할 수 밖에 없다!
그럼으로 중복이 발생하는 것을 방지하기 위해서 Set을 사용했다!
그리고 dfs를 통해 str을 만들어주도록 하자
소수 구하기
소수를 구하는 효율이 좋은 방법은 에라스토테네스의 체를 이용하는 방법이고, 여러 숫자가 소수인지 판단할 때 좋은 방법으로 알고 있다.
그러나 해당 문제에서는 만들 수 있는 숫자가 일단 제한적이라는 부분이 있고, 1~1000까지 이런 경우라면 더 효율적이겠지만 해당 문제에서는 그냥 2~n까지 소수인지 확인하는 것도 그렇게 오래는 걸리지 않을 거라 생각해서 그냥 일반 반복문으로 풀이!
💻 해결코드
import java.util.*;
class Solution {
static HashSet<String> list= new HashSet<>();
static int[] visited;
static String ary;
public int solution(String numbers) {
ary = numbers;
visited= new int[ary.length()];
int answer = 0;
findAll(0,"");
Iterator<String> iter = list.iterator(); // set을 Iterator 안에 담기
while(iter.hasNext()) { // iterator에 다음 값이 있다면
//System.out.println("iterator : " + iter.next()); // iter에서 값 꺼내기
//이게 소수인가?
int isPrime = 0;
int cur = Integer.parseInt(iter.next());
System.out.println(cur);
for(int i = 2; i * i <= cur; i++){
if(cur % i == 0){
isPrime = 1;
break;
}
}
if(cur != 1 && isPrime == 0)
answer++;
}
return answer;
}
public static void findAll(int depth,String cur){
if(depth == ary.length()){
return;
}
for(int i = 0 ; i < ary.length(); i++){
if(visited[i] == 0){
visited[i] = 1;
String temp = cur + ary.charAt(i);
if(temp.charAt(0) != '0')
list.add(temp);
findAll(depth+1, temp);
visited[i] = 0;
}
}
}
}