[Java Algorithm] 프로그래머스 Lv.2_ 소수 찾기

[문제]

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

[Algorithm]

처음에는 단순히 numbers 문자열의 문자들을 배열에 담고 그 배열의 조합들을 찾아내서 소수인지 판단하고 return하면 된다고 생각했다.

그런데 그러면 중복 제외 처리를 따로 해야하는 문제점이 발생..

그리고 배열의 조합을 어떤식으로 만들어야할지 감이 안왔다 -

 

그래서 결국 클로드와 구글 검색을 통해 공부함

 

1. 중복 방지를 위해 Set을 활용해 조합을 저장할 set 선언

2. 재귀함수를 이용해 순열 생성 → 모든 조합을 만들어 set에 저장

3. 에라토스테네스의 체를 이용해 소수 찾기

4. 개수 카운트해서 반환

 

[Code]

import java.util.*;

class Solution {
    // 중복 방지를 위한 set 선언
    Set<Integer> set = new HashSet<>();
    
    public int solution(String numbers){
    	permutation("", numbers);	// 숫자 조합을 만들어 set에 저장
        
        int count = 0;
        for(int num : set) {
        	if(isPrime(num)) count++;
        }
        
        return count;
    }
    
    // 재귀를 이용해 순열 생성
    public void permutation(String prefix, String str) {
    	if(!prefix.equals("")) {
        	set.add(Integer.parseInt(prefix)); //조합된 숫자를 set에 추가
        }
        
        for(int i=0; i < str.length(); i++){
        	//i번째 문자를 제외하고 다음 순열 생성
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1));
        }
    }
    
    // 소수 판별 함수
    public boolean isPrime(int n) {
        if (n < 2) return false;

        // 에라토스테네스 체
        for (int i = 2; i <= (int)Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }

        return true;    		
    }
}

 

[+ 다른 사람 풀이]

import java.util.HashSet;

class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

    public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();

        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++) permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}

 

순열 함수가 기가 맥힌다는 댓글들이 백만개 ..

위 코드랑 다른 점은 set을 solution안에 선언해서 permutation 함수 사용시 set까지 매개변수로 넘겨준다

근데 이 문제에서는 어차피 set을 한 번만 쓸거라 굳이 이렇게 할 이유는 없을 것 같다 ..

 

또 여기서 궁금한 점.. 

왜 isPrime에서 i를 3부터 시작하고 굳이 while 문에서 2인 경우를 ++ 해주는걸까 ?

그냥 소수 판별 함수에서 2를 포함시켜도 되는 문제 아닌가 . . . 

반복문에서 짝수를 제외하고 도는게 훨씬 효율성이 높은건가?!

 

아시는 분 댓글점여..