코딩테스트 연습 > 소수 찾기 (순열)

 

 

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;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요