프로그래머스[Level2] - 소수 찾기

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

 

1. 종이 조각으로 만들 수 있는 수 찾기 - 순열

2. 소수 찾기

 

import java.util.*;
class Solution {
    public static boolean visit[];
    public static HashSet<Integer> set = new HashSet<Integer>();
    public static String nums;
    public int solution(String numbers) {
        int answer = 0;
        nums = numbers;
        visit = new boolean[nums.length()];
        Arrays.fill(visit,false);
        
        //1. 종이조각으로 만들 수 있는 수 저장
        for(int i=0;i<nums.length();i++){
            // System.out.println("===i :"+i+"====");
            visit[i]=true;
            dfs(i,String.valueOf(nums.charAt(i)));   
            visit[i]=false;
            
        }
        
        //2. 소수 판별
        Iterator iter = set.iterator();
        while(iter.hasNext()){
            boolean flag= false;
            Integer n = (Integer)iter.next();
            if(n == 1 || n==0)
                flag=true;
            for(int i =2;i<n;i++){
                    if(n%i==0)
                        flag=true;
                
            }
            if(!flag){
                System.out.println(n);
                answer++;
            }
        }
        
        System.out.println(set);
        return answer;
    }
    
    public void dfs(int idx, String num) {
        //종료조건
        //자리수 이상?
        if(num.length()>nums.length()){
            return;
        }
        // System.out.println(num);
        set.add(Integer.parseInt(num));
        
        for(int i=0;i<nums.length();i++){
            if(visit[i])
                continue;
            
            
            visit[i]=true;
            dfs(i,num+nums.charAt(i));
            visit[i]=false;
            
        }
        
    }
}

완전 올만에 머리를 다시 쓸겸 알고리즘 공부를 해봤다. 오랜만에 해서 역시,, 허덕이는군 ^_ㅜ

머리야~ 말랑말랑해져라