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

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

해당 문제는 재귀방식으로 주어진 숫자 배열중 3개를 선택해 더한 숫자가 소수이면 카운팅하고 아닌경우 0을 return 하여 최종적으로 만들수 있는 소수의 갯수를 return 해야하는 문제였습니다. 해당 문제는 재귀 형식으로 풀었고, 넘겨주는 nums는 넘어온 nums에서 자신 이후의 숫자들을 넘겨 최종 depth가 2인 경우 남은 배열의 숫자들을 넘어온 addedNum과 더해 해당 숫자가 소수인경우 1을 return 하고 아니면 0을 return하는 식으로 구현했습니다.

public int solution(int[] nums) {
        return dfs(0, 0, nums);
    }
    private int dfs(int depth, int addedNum, int[] nums) {
        int answer = 0;

        if (depth == 2) {
            for (int i = 0; i < nums.length; i++) {
                answer += isPrimeNumber(addedNum + nums[i]) ? 1 : 0;
            }
            return answer;
        }

        for (int i = 0; i < nums.length; i++) {
            answer += dfs(depth + 1, addedNum + nums[i], Arrays.copyOfRange(nums, i + 1, nums.length));
        }

        return answer;
    }

    private boolean isPrimeNumber(int num) {
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }