소수찾기

문학적인유사성·2022년 2월 19일
0

language

목록 보기
1/24

SSAFY에 있으면서 했던 코테를 잠시 놓았더니 전부다 까먹어서
순열 조합 부분집합등 전부다 못푸는 지경이 되버렸다 ㅠㅠ
처음부터 다시 하려고한다!!

접근은
0. 완전 탐색을 사용 할수있는가?

  • 숫자가 가능한 모든 선택지를 뽑아낸다.
  • 1 ~ N자리수를 만들어내서 dfs를 이용해 찾는다.
  • answer_list arr에 값이 있는지 없는지 확인한다(Set으로 하면 그냥 알아서 걸러질 것같다. )
  1. answer_list arr에 에라토네스체를 이용하여 소수를 찾을 수있는가?
  • 소수찾기 알고리즘을 이용하여 소수를 찾는다
  • 맞으면 answer++

array_list버전

//20220219
import java.util.*;

class Solution {
    
    static private ArrayList<Integer> answer_list = new ArrayList<Integer>();
    static private int[] check = new int[10];
    
    public int solution(String numbers) {
        
        int answer = 0; 
        String tmp ="";
        
        
        for(int i=0;i<numbers.length();i++){
            dfs("", numbers, i+1);
        }
        
        /*
        for(int i : answer_list){
            System.out.println(i);
        }*/
        
        for(int i=0;i<answer_list.size();i++){
            if(check(answer_list.get(i))==true){
                answer++;
            }else{
                
            }
        }
        
        return answer;
    }
    
    private void dfs(String now, String numbers,int size){
        if(now.length()==size){
            int temp_num = Integer.parseInt(now);
            if(answer_list.contains(temp_num)==false){
                answer_list.add(temp_num);
            }
            return;
        }
        
        for(int i=0;i<numbers.length();i++){
            if(check[i]==0){
                check[i]=1;
                now+=numbers.charAt(i);
                
                dfs(now, numbers, size);
                
                check[i]=0;
                now= now.substring(0, now.length()-1);
            }
        }
        
        
    }
    
    private boolean check(int num){
        if(num==0) return false;
        if(num==1) return false;
        
        for(int i=2;i<num;i++){
            if(num % i ==0){
                return false;
            }
        }
        
        return true;
       
    }
}

set연습 버전

import java.util.*;

class Solution {
    static private boolean[] check = new boolean[10];
    static Set<Integer> answer_set = new HashSet<Integer>();
    
    public int solution(String numbers) {
        int answer = 0;
        String temp = "";
        
        for(int i=0;i<numbers.length();i++){
            dfs(temp, numbers, i+1);
        }
        
        
        Iterator<Integer> itr = answer_set.iterator();
        
        while(itr.hasNext()){
            int check = itr.next();
          
            if(isprime(check)==true){
                answer++;
            }
        }
        
        return answer;
    }
    private void dfs(String temp, String numbers, int size){
        if(temp.length()==size){
            int temp_number = Integer.parseInt(temp);
            answer_set.add(temp_number);
            
            return;
        }
        
        for(int i=0;i<numbers.length();i++){
            if(check[i]==false){
                check[i]=true;
                
                temp += numbers.charAt(i);
                dfs(temp, numbers, size);
                
                check[i]=false;
                temp=temp.substring(0, temp.length()-1);
                
            }
            
        }
        
        
        
    }
    
    private boolean isprime(int num){
        if(num==0) return false;
        if(num==1) return false;
        
        for(int i=2;i<num;i++){
            if(num%i==0){
                return false;
            }
        }
        
        return true;
    }
}
profile
Are you nervous? Don't be

0개의 댓글