[Java] 소수 만들기

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

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

 

class Solution {
    public int solution(int[] nums) {
        int answer = 0, count = 3;
        boolean[] visited = new boolean[nums.length];
        answer = combination(nums, visited, 0, 0, count);
        
        return answer;
    }
    
    public int combination(int[] nums, boolean[] visited, int start, int depth, int count) {
        int sosuCount = 0;
        
        if(depth == count) {
            int sum = 0;
            for(int i = 0; i < nums.length; i++) {
                if(visited[i]) {
                    // System.out.print(nums[i] + " ");
                    sum += nums[i];
                }
            }
            // System.out.println();
            if(isSosu(sum)) {
                return 1;
            }
            return 0;
        }
        
        for(int s = start; s < nums.length; s++) {
            if(!visited[s]) {
                visited[s] = true;
                sosuCount += combination(nums, visited, s + 1, depth + 1, count);
                visited[s] = false;
            }
        }
        
        return sosuCount;
    }
    
    public boolean isSosu(int sum) {
        boolean sosu = true;
        
        for(int i = 2; i <= Math.sqrt(sum); i++) {
            if(sum % i == 0) {
                sosu = false;
                break;
            } 
        }
        
        return sosu;
    }
    
    
}

이 문제에서는 조합 알고리즘을 활용하여 해결하였다.

combination 메서드로 원하는 개수만큼의 조합이 나오는지 확인한 후, 응용하여 그 조합이 소수인지를 isSosu 메서드로 확인하였다.

재귀를 썼기 때문에 머릿속으로 이해를 한다면 좋긴 하겠지만, 이해가 안되면 디버깅을 필수로 해봐야 한다.

인텔리제이로 디버깅을 해도 처음엔 이해가 잘 안됐었지만, 너무 어렵게 생각했었을 뿐 방문했는지 판단하는 visited의 역할만 제대로 이해한다면 금방 이해할 수 있을 것이다.

 

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/12977