[Programmers] LV2 - 소수 찾기

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

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

 

 

 

문제 파악

 

주어진 숫자 문자열을 가지고 소수를 몇 개 만들 수 있는지 구하는 문제이다.

 

순열 + 소수 찾기 문제인 것인데

1. 소수 찾는 방법은 에라토스테네스의 체로 최대 범위 10,000,000까지의 소수를 미리 구했다.

( 10,000,000 까지 구한 이유 number의 최대길이는 7 , 범위는 0~9로만 이루어져 있기 때문에 최대 9,999,999까지의 숫자까지 만들 수 있다고 판단했다.)

2. 주어진 숫자 문자열의 순열을 구한다. (순서에 따라 숫자가 달라지기 때문에 순열 구현)

2-1. 중복 값은 필요 없기 때문에 자료구조는 HashSet을 이용하여 데이터 삽입

3. 소수인지 판단 하여 answer 값을 증가시킨다.

 

import java.util.*;

class Solution {
	boolean[] eratos = new boolean[10000000];
    HashSet<Integer> hs = new HashSet<Integer>();
    
    public int solution(String numbers) {
        int answer = 0;
        
        permutation("",numbers);
        
        int max = Collections.max(hs);
        
        IsPrime(max);
                
        Iterator<Integer> it = hs.iterator();
        
        while(it.hasNext()) {
        	int num = it.next();
        	if(eratos[num]) {
        		answer++;
        	}
        }
        
        return answer;
    }
    
    private void permutation(String str, String numbers) {
		int n = numbers.length();
		if(!str.equals("")) {
			hs.add(Integer.valueOf(str));
		}
		
		for(int i=0; i<n;i++) {
			permutation(str+numbers.charAt(i), numbers.substring(0,i)+ numbers.substring(i+1,n));
		}
		
	}

	// Hash 중에 만들어진 최대 수 까지만 돌면 되지 않을까?
    public void IsPrime(int n){
    	Arrays.fill(eratos,true);
        eratos[0] = false;
        eratos[1] = false;
        
        for(int i=2;i<=Math.sqrt(n);i++)
        {
            if(!eratos[i]){
                continue;
            }
            for(int j= i*2;j<=n;j+=i){
                eratos[j] = false;
            }
        }
        return;
    }   
    
}

 

많이 부족한 실력이기에 개선의 여지나 잘못된 부분을 지적해주신다면 감사하겠습니다.