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

fsm12·2023년 6월 24일

프로그래머스

목록 보기

19/57

문제링크

문제 이해

[ 입력형태 / 조건 ]

nums
숫자들이 들어있는 배열 | [1,2,3,4] | 숫자의 개수는 3개 이상 50개 이하, 최대 각 원소는 1 이상 1,000 이하의 자연수

[ 문제 ]

=> nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return

[ 풀이 ]

에라토스테네스의 체를 이용해 소수를 미리 구하고, 조합을 통해 3개를 뽑은 뒤 소수인지 판별하여 cnt 1 증가

코드

> [성공] 1차 시도 : 기본 에라토스테네스의 체, 조합 이용

생각한 풀이 그대로 구현

class Solution {
    public int solution(int[] nums) {
        boolean[] isNotPrime = new boolean[3000];
        for(int i=2; i<3000; i++){
            for(int j=2; i*j<3000; j++){
                isNotPrime[i*j] = true;
            }
        }
        return nCr(-1,0,0,nums,isNotPrime);
    }
    
    public int nCr(int start, int cnt, int sum, int[] nums, boolean[] isNotPrime){
        if(cnt == 3){
            if(!isNotPrime[sum]){
                return 1;
            }
            return 0;
        }
        
        int cur_ans = 0;
        for(int i=start+1; i<nums.length; i++){
            cur_ans += nCr(i, cnt+1, sum+nums[i], nums, isNotPrime);
        }
        return cur_ans;
    }
}

=> 에라토스테네스의 체를 최적화 해야겠음

> [성공] 2차 시도 : 최적화된 에라토스테네스의 체, 조합 이용

에라토스테네스의 체 최적화를 위해 루트까지만 실행

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        boolean[] isPrime = new boolean[3000];
        Arrays.fill(isPrime, true);
        
        for(int i=2; i<=(int) Math.sqrt(3000); i++){
            if(isPrime[i]){
                for(int j=i*i; j<3000; j+=i){
                    isPrime[j] = false;
                }
            }
        }
        return nCr(-1,0,0,nums,isPrime);
    }
    
    public int nCr(int start, int cnt, int sum, int[] nums, boolean[] isPrime){
        if(cnt == 3){
            if(isPrime[sum]){
                return 1;
            }
            return 0;
        }
        
        int cur_ans = 0;
        for(int i=start+1; i<nums.length; i++){
            cur_ans += nCr(i, cnt+1, sum+nums[i], nums, isPrime);
        }
        return cur_ans;
    }
}

=> Arrays.fill()로 3000 사이즈의 배열에 초기값을 설정하는 과정을 추가해야 했음

> [성공] 3차 시도 : 최적화된 에라토스테네스의 체, 조합 이용

Arrays.fill() 과정을 생략하기위해 boolean 배열에 반대로 담음

class Solution {
    public int solution(int[] nums) {
        boolean[] isNotPrime = new boolean[3000];
        
        for(int i=2; i<=(int) Math.sqrt(3000); i++){
            if(!isNotPrime[i]){
                for(int j=i*i; j<3000; j+=i){
                    isNotPrime[j] = true;
                }
            }
        }
        return nCr(-1,0,0,nums,isNotPrime);
    }
    
    public int nCr(int start, int cnt, int sum, int[] nums, boolean[] isNotPrime){
        if(cnt == 3){
            if(!isNotPrime[sum]){
                return 1;
            }
            return 0;
        }
        
        int cur_ans = 0;
        for(int i=start+1; i<nums.length; i++){
            cur_ans += nCr(i, cnt+1, sum+nums[i], nums, isNotPrime);
        }
        return cur_ans;
    }
}