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

프로그래머스 소수 만들기 - JAVA

문제 설명

1. 숫자들이 들어있는 배열 nums가 매개변수로 주어짐.
2. nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return.

제한사항

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

문제 풀이

1. 에라스토테네스의 체를 사용하여 3000까지 숫자의 소수 유무를 저장.
2. dfs탐색을 사용하여 3개의 수의 모든 조합을 탐색.
3. 조합의 숫자를 더했을 떄 소수가 되는 걍우 answer를 1증가.

소스코드

import java.util.*;

class Solution {
    public int answer = 0;
    public boolean[] isPrime;

    public int solution(int[] nums) {
        isPrime = new boolean[3001];

        eratostenes();

        dfs(0, 0, 0, nums);

        return answer;
    }

    public void eratostenes() {
        for (int i = 2; i <= 3000; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i <= 3000; i++) {
            for (int j = i * i; j <= 3000; j += i) {
                isPrime[j] = false;
            }
        }
    }

    public void dfs(int depth, int start, int sum, int[] nums) {
        if (depth == 3) {
            if (isPrime[sum]) answer++;
            return;
        }

        for (int i = start; i < nums.length; i++) {
            dfs(depth + 1, i + 1, sum + nums[i], nums);
        }
    }
}