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

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때,

nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이

먼저 소수가 되는 조건을 찾아보려고 하였다.
소수 + 소수는 소수가 되는가?? 아니다.

소수 + 합성수는 소수가 되는가?? 그것도 아니다.
여러 생각들을 해보았는데, 역시 아무런 규칙이 없다.
따라서 이건 전수조사를 해야 한다고 생각을 하였다.

주어진 nums배열에서 3가지의 수를 더한 후 소수인지판별을 모든 조합을 따져야 한다.
배열에서 3가지 배열을 고르는 로직을 백트래킹을 이용하여 구현하였고, 그렇게 구한 sum을 소수인지 판별하도록 하였다.

import java.util.*;
import java.lang.*;

class Solution {
    static int sum = 0;
    static int answer = 0;

    public int solution(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        chooseNum(nums, visited, 0, 0);

        return answer;
    }

    static void chooseNum(int[] nums, boolean[] visited, int start, int depth) {
        if (depth == 3) {
            if (check()) {
                answer++;
            }

            return;
        }


        for(int i = start; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sum += nums[i];
                chooseNum(nums, visited, i + 1, depth + 1);
                visited[i] = false;
                sum -= nums[i];
            }
        }
    }

    static boolean check() {
        for(int i = 2; i < sum; i++) {
            if (sum % i == 0) {
                return false;
            }
        }

        return true;
    }
}

https://github.com/Win-9/Algorism/tree/main/programers/%EC%86%8C%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0