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

문제

---

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

 

 

풀이

---

소수를 에라토스테네스체로 미리 구했다.

여기서 수의 정해주었지만 조금더 적은 수를 가지고 하고싶어서, 값의 최댓값은 단순하게 모든 수의 합으로 했다.

 

for(int i = 0 ; i < nums.length ; i++){
	sum += nums[i];
}
boolean[] primeNumber = new boolean[sum + 1];
        
for(int i = 2; i * i < sum ; i++){
	if(primeNumber[i])
		continue;
	for(int j = i * i ; j <= sum ; j += i){
		primeNumber[j] = true;
	}
}

위의 코드에서 처럼 모든수의 합을 구한 뒤, 에라토스 테네스체를 구해 나중에 나온 합이 소수인지 계속해서 판단하지 않아도 되게 했다.

 

숫자 조합을 구하는 코드는 재귀를 이용해서 구현하였다.

static void Recusion(boolean[] primeNumbers,int[] nums, int size, int sum, int idx, int r){
        
	if(size == r){
		if(sum >= 2 && !primeNumbers[sum])
			answer++;
            
		return;
	}
        
        
	for(int i = idx + 1; i < nums.length ; i++){
		Recusion(primeNumbers, nums, size, sum + nums[i], i, r + 1);
	}
}

 

<전체코드>

class Solution {
    
    static int answer = 0;
    public int solution(int[] nums) {
               
        int sum = 0;
        for(int i = 0 ; i < nums.length ; i++){
            sum += nums[i];
        }
        boolean[] primeNumber = new boolean[sum + 1];
        
        for(int i = 2; i * i < sum ; i++){
            if(primeNumber[i])
                continue;
            for(int j = i * i ; j <= sum ; j += i){
                primeNumber[j] = true;
            }
        }
        
        for(int i = 0 ; i < nums.length ; i++){
            Recusion(primeNumber, nums, 3, nums[i], i, 1);
        }
        
        return answer;
    }
    
    static void Recusion(boolean[] primeNumbers,int[] nums, int size, int sum, int idx, int r){
        
        if(size == r){
            if(sum >= 2 && !primeNumbers[sum])
                answer++;
            
            return;
        }
        
        
        for(int i = idx + 1; i < nums.length ; i++){
            Recusion(primeNumbers, nums, size, sum + nums[i], i, r + 1);
        }
    }
}