[ 프로그래머스 ] 소수 만들기 ( 자바 )

[ 프로그래머스 ] 소수 만들기 ( java )

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

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.

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

 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12977

프로그래머스

 

 

 

 

핵심 

1. 3Cn

dfs를 이용해서 3Cn 선택 

 

2. 소수 만들기 

에라토스테네스의 체, 또는 '루트 값' 미만 2이상 수를 모두 검사해보기 

 

 

 

주의 

에라토스테네스 체로 풀 경우 배열의 크기를 적어도 3000으로 해야한다.

왜냐하면, 원소 최대가 1000이기 때문이다. 

 

원소 최대 범위만 보고 배열 범위를 정했다가 처음에 틀렸다. 

만약, 회사 코테에서 나왔는데 에라토스테네스 체로 풀었다면 틀렸을 것 같다. 

 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요! 

 

 

 

 

코드

import java.util.*;
 
public class Solution {
    public int solution(int[] nums) {
        boolean[] isPrime = new boolean[3001];
        Arrays.fill(isPrime, true);
        isPrime[1] = false;
        setPrime(isPrime);
        return dfs(nums, isPrime, 0, 0, 0);
    }
    
    static void setPrime(boolean[] isPrime) {
        for(int num = 2 ; num <= 3000; num++) {
            if(isPrime[num]) {
                for(int other = num*2 ; other <= 3000 ; other += num) {
                    isPrime[other] = false;
                }
            }
        }
    }
    
    static int dfs(int[] nums,boolean[] isPrime, int val, int i, int cnt) {
        if(cnt == 3) {
            if(isPrime[val])
                return 1;
            else
                return 0;
        }
        if(i == nums.length) {
            return 0;
        }
        
        return dfs(nums,isPrime, val, i+1, cnt) + dfs(nums,isPrime, val+nums[i], i+1, cnt+1);
    }
}