프로그래머스/Lv.2
코딩테스트 연습 > 소수 찾기 (순열)
아찌방
2024. 1. 29. 23:52
https://school.programmers.co.kr/learn/courses/30/lessons/42839
풀이 - 나의 생각
순열을 사용해서 numbers로 만들 수 있는 모든 조합을 찾아가면서
Set에 저장(중복 제거를 위해)
그 후 소수의 갯수를 체크하면 된다.
코드
import java.util.*;
import java.util.stream.Collectors;
class Solution {
static boolean[] visited;
static String[] nums;
static Set<Integer> set;
public int solution(String numbers) {
set = new HashSet<>();
visited = new boolean[numbers.length()];
nums = numbers.split("");
makeNum(0, "");
return set.stream()
.filter(this::isPrime)
.collect(Collectors.toList())
.size();
}
public static void makeNum(int cnt, String stNum){
if(!stNum.isEmpty()) {
set.add(Integer.parseInt(stNum));
}
for(int i =0; i < nums.length; i++){
if(visited[i]) continue;
visited[i] = true;
makeNum(cnt+1, stNum+nums[i]);
visited[i] = false;
}
}
public boolean isPrime(int num){
if(num < 2) return false;
for(int i = 2; i <= Math.sqrt(num); i++){
if(num%i == 0) return false;
}
return true;
}
}
728x90