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

문제 설명

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

제한사항

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

 

소수 만들기

소수 만들기 문제를 풀어보자. 이 문제를 풀기 위해서 순열과 조합에 대해서 먼저 공부하였다.

n개의 배열에서 r개의 원소를 선택하는 조합 작성하면 나머지는 간단하게 구현이 가능하다.

 

작성 코드

using System;

class Solution
{
    public int solution(int[] nums)
    {
        int[] comb = new int[3];
        int answer = 0;
        
        Combination(ref answer, nums, comb, 3, 0, 0);

        return answer;
    }
    
    public void Combination(ref int count, int[] array, int[] comb, int r, int index, int depth)
    {
        if (r == 0)
        {
            int sum = 0;

            for (int i = 0; i < comb.Length; i++)
            {
                sum += comb[i];
            }

            if (IsPrimeNumber(sum))
            {
                count++;
            }
        }
        else if (depth == array.Length)
        {
            return;
        }
        else
        {
            comb[index] = array[depth];

            Combination(ref count, array, comb, r - 1, index + 1, depth + 1);
            Combination(ref count, array, comb, r, index, depth + 1);
        }
    }
    
    public bool IsPrimeNumber(int number)
    {
        if (number <= 1) return false;

        for (int i = 2; i < number; i++)
        {
            if (number % i == 0)
            {
                return false;
            }
        }

        return true;
    }
}

 

같이 읽으면 좋은 글

순열과 조합