[ 완전탐색 Level2 ] 프로그래머스 소수 찾기 - 자바 Java

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

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

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

입출력 예

numbers	return
17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

---

해당 문제를 자세히 생각해 보면 순열과 소수를 찾는 2가지가 결합된 문제입니다. 순열이랑 소수 찾는 방법을 모른다면  어려울 수 있습니다. 공부를 하던 중 순열로 숫자를 조합하는 효율적인 알고리즘을 찾았습니다. 다음과 같습니다.

 

소수 찾기 자바 코드

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 void permutation(String prefix, String str, HashSet<Integer> set) { 
        int n = str.length();        
        if(!prefix.equals("")) {
           set.add(Integer.valueOf(prefix)); //스트링을 Interger로 변환
        }
        
        for (int i = 0; i < n; i++){
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
        }

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

 

해당 코드의 순열 알고리즘은 외우는 것을 추천드립니다. 두고두고 활용성이 높을 것 같습니다.

정말 이렇게도 만들 수 있구나라는 생각이 들었습니다.

 

정리

그리고 소수 찾기 알고리즘의 설명을 덧붙이자면 소수에는 다음과 같은 수학적 증명이 있습니다.

1. n이 n의 제곱근보다 크지 않은 어떤 수로도 나눠지지 않습니다.  ex) 9는 9의 제곱근인 3보다 크지 않은 숫자 2로 나눠지지 않습니다.
2. 1, 2를 제외한 소수는 2로 나누면 나머지가 있습니다. ex) 5, 7, 11, 17... 2로 나누면 전부 나머지가 존재합니다.
3. 소수는 2 ~ (N-1) 범위에서 약수를 가지지 않는다.                                                                                                            ex) 소수 5는 2~4 범위에서 약수(어떤 수나 식을 나누어 나머지가 없이 떨어지는 수)를 가지지 않습니다. 또한 약수가 존재하는 숫자의 약수들 중 반은 1 ~ sqrt(N) 범위에 존재한다.

 

sqrt(N)까지만 하는 이유?

소수의 판별 여부는 결국 약수가 있냐 없냐를 찾아보는 과정이기 때문에 그렇습니다.

예를 들어서 12의 약수는 1 2 3 4 6 12입니다. 약수는 항상 짝으로 존재합니다.

 

12 = 1 X 12 = 2 X 6 = 3 X 4 -> 즉 약수를 찾을 때, 1, 2, 3 까지만 찾으면, 나머지 4, 6, 12는 짝으로써 자동으로 결정된다는 겁니다. 그리고 3까지 찾는 근거는 루트 12 가 3.xxx입니다. 7이건 어떤 자연수이건 같은 논리가 적용됩니다. 앞쪽에 약수가 없다면, 뒤쪽에는 당연히 짝이 없을 것입니다.

 

---

소수 찾기를 완전 이해하시라고 에라토스테네스의 체 링크를 남깁니다.

그러면 소수 찾기에 대해서 이해도가 훨씬 높아지실 겁니다.

 

 

감사합니다.