이번에 풀어본 문제는
프로그래머스 소수 만들기 입니다.

📕 문제 링크

❗️코드

class Solution {
    static int answer;
    static int maxValue;
    static int size;
    static int [] n;
    static boolean [] isNotPrime;
    public int solution(int[] nums) {
        answer = 0;
        n = nums;
        //중복없이 숫자 하나의 최댓값이 1000이므로 넉넉하게 nums배열의 크기 * 1000까지의 소수를 구함.
        size = nums.length;
        maxValue = size * 1000;
        isNotPrime = new boolean[maxValue+1];
        isNotPrime[0] = isNotPrime[1] = true;
        setPrime();

        comb(0,0,0);
        return answer;
    }
    static void setPrime() {
        for (int i = 2; i * i <= maxValue; i++){
            if (!isNotPrime[i]){
                for (int j = i * i; j <= maxValue; j += i){
                    isNotPrime[j] = true;
                }
            }
        }
    }
    static void comb(int idx, int sum,int depth) {
        if (depth == 3){
            if (!isNotPrime[sum]) answer++;
            return;
        }

        for (int i = idx; i < size; i++){
            comb(i+1,sum + n[i], depth + 1);
        }
    }
}

📝 풀이

주어진 배열에서 3개를 골라 합을 구했을 때, 그 합이 소수인 것의 개수를 구하는 문제입니다. 적절한 범위까지의 소수를 구해놓고, 만들 수 있는 모든 경우의 수중 소수 인 것의 개수를 카운트 하는 방식으로 해결했습니다.
에라토스테네스의 체 , 조합을 활용했습니다.

📜 후기

요즘 시간이 부족하여 문제를 많이 못풀고 있는데, 가볍게 풀기 좋았던 문제였습니다 ^~^