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

📚 소수 만들기

[JAVA] 프로그래머스 Level 1.

코딩테스트 연습 - 소수 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

문제

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

제한사항

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

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

문제 해결 방안

 배열에 들어있는 숫자 3개를 더한 값이 소수인지 판단하는 문제입니다.

배열에 들어있는 숫자 3개 -> 중복 x, 숫자를 더한 값 -> 순서가 상관없음 

- 즉 조합을 의미

조합을 이용하여 숫자 3개를 구한 뒤 소수인지 판단한다.

소스 코드

class Solution {
    int answer = 0;
    public int solution(int[] nums) {
        combination(nums, new int[3], new boolean[nums.length], 0, 0, 3);
        return answer;
    }
    
    public boolean combination(int[] nums, int[] outs, boolean[] visited, int start, int depth, int k) {
        if(depth == k) {
            int sum = 0;
            for(int n : outs) {
                sum+=n;
            }
            
            for(int i=2; i*i<=sum; i++){
                if(sum % i == 0) return false;
            }
            answer +=1;
            return true;
        }
        
        for(int i=start; i<nums.length; i++) {
            if(!visited[i]) {
                outs[depth] = nums[i];
                visited[i] = true;
                combination(nums, outs, visited, i, depth+1, k);
                visited[i] = false;
            }
        }
        return false;
    }
}

풀고나서…

소수 구하기, 조합, 순열 알고리즘을 알아두자