[프로그래머스,Java] Level2:소수 찾기

 

문제분석

 

조금 정직한 문제다.

 

1. numbers의 카드들이 존재하는데, numbers의 카드들을 재배열시켜서 만들수있는 숫자를 만든다.

 

2.만들어진 숫자들이 소수인지 확인한다.

 

3.소수의 갯수를 센다.

 

 

 

1. 순열 알고리즘으로  모든 숫자를 재배열시킨다.

->순열알고리즘은 구글링하면 나오지만, 돌아가는 로직은 알아두는게좋다.

 

->재배열한 숫자를 저장하는 리스트 하나 생성

 

1-2. 모든 경우의수를 정제한다.

 

EX) 00045, 001, 024 같은 숫자들은 45, 1,24 로 변환시켜야한다.  String -> Integer 변환

EX) 소수는 2부터 시작하므로, 0,1인 숫자는 제거한다.

 

2.소수를 판별하는 알고리즘을 사용한다. (에라토네스의체)

->구글링하면 나온다. 

 

3.소수 의갯수세기.

문제풀이

import java.util.*;
class Solution {
    static List<String> cases = new LinkedList<>();
    
    public int solution(String numbers) {
        int answer = 0;
        List<String> cards = new LinkedList<>();
        List<String> result = new LinkedList<>();
        String[] num_arr=numbers.split("");
        
        for(String data: num_arr){
            cards.add(data);
        }
        
        for(int i=1;i<=numbers.length();i++){
           reculsion(cards,result,numbers.length(),i);
        }
        
        Set<Integer> case_dis =new HashSet<>();
        for(String data:cases){
            // 0과 1인경우는 제외하기위함. 2이상부터
            if(Integer.valueOf(data)>1){
            case_dis.add(Integer.valueOf(data));
            }
        }
        
        for(int data:case_dis){  
            boolean flag =true;
            if(data==2){
                answer++;
                continue;
            }         
            for(int i=2;i<=Math.sqrt(data);i++){
                if(data%i==0){
                    flag=false;
                    break;
                }
        
                flag=true;
        
            }
            if(flag==true){
                answer++;
            }
        }
        System.out.println(case_dis.toString());
        
        return answer;
    }
     private static void reculsion(List<String> cards, List<String> result, int n, int r) {
        if (r == 0) {
            String temp="";
            for(String data:result){
                temp+=data;
            }
            cases.add(temp);
            return;
        }
 
        for (int i = 0; i < n; i++) {
 
            result.add(cards.remove(i));
            reculsion(cards, result, n - 1, r - 1);
            cards.add(i, result.remove(result.size() - 1));
        }
    }
}