[Lv.1] 소수 만들기 [프로그래머스_코딩테스트] [Brute Force] [25분]

🔍 문제 요약

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

프로그래머스

숫자들 nums가 주어지고 해당 값들 중에서 숫자 3개를 합쳐서 소수가 되는 모든 경우의 수의 개수를 구하는 문제

🧠 나의 접근 방식과 시행착오

단순하게 생각해서 문제를 풀려고 시도했다. 다만 소수 구하는 부분에서 Sqrt를 써서 개수를 줄이려고 시도를 했으나 다른 부분에서 실수가 나는 바람에 해당 코드를 지웠다.. 문제를 이해할 때 합계가 같으면 경우의 수를 제외시키는 것으로 착각을 해서 Dictionary를 만들고 sum 값을 넣어서 걸렀던게 실수.

using System;
using System.Collections.Generic;

public class Solution
{
    public bool CheckSoSoo(int num)
    {
        for (int i = 2; i < num; i++)
        {
            if (num % i == 0)
            {
                return false;
            }
        }

        return true;
    }
    
    /// <summary>
    /// 소수 만들기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/12977
    /// </summary>
    public int solution(int[] nums)
    {
        int answer = 0;
        int numLen = nums.Length;

        for (int i = 0; i < numLen - 2; i++)
        {
            for (int j = i + 1; j < numLen - 1; j++)
            {
                for (int k = j + 1; k < numLen; k++)
                {
                    int sum = nums[i] + nums[j] + nums[k];

                    if (CheckSoSoo(sum))
                    {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var nums1 = new[] { 1, 2, 3, 4 };
        var nums2 = new[] { 1, 2, 7, 6, 4 };
        
        Console.WriteLine(sl.solution(nums1));
        Console.WriteLine(sl.solution(nums2));
    }
}

✅ 풀이 코드

핵심은 소수를 구하는 IsPrime 부분을 Sqrt로 해서 최소한으로 줄이는 부분이다. 자주 나오는 부분이라서 기억해두고 사용하면 좋을 것.

using System;

public class Solution
{
    public bool IsPrime(int num)
    {
        if (num < 2) return false;
        int sqrt = (int)Math.Sqrt(num);
        for (int i = 2; i <= sqrt; i++)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }

    public int solution(int[] nums)
    {
        int count = 0;
        int len = nums.Length;

        for (int i = 0; i < len - 2; i++)
        {
            for (int j = i + 1; j < len - 1; j++)
            {
                for (int k = j + 1; k < len; k++)
                {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (IsPrime(sum))
                        count++;
                }
            }
        }

        return count;
    }
}

 

추가로 에라토스테네스의 체로 소수 배열을 미리 구해두고 활용하는 방법도 있어서 해당 방법도 적어두었다.

using System;

public class Solution
{
    // 에라토스테네스의 체로 소수 배열 생성
    public bool[] GetPrimeTable(int max)
    {
        bool[] isPrime = new bool[max + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i * i <= max; i++)
        {
            if (!isPrime[i]) continue;

            for (int j = i * i; j <= max; j += i)
            {
                isPrime[j] = false;
            }
        }

        return isPrime;
    }

    public int solution(int[] nums)
    {
        int maxSum = 3000;  // 최대 합
        var isPrime = GetPrimeTable(maxSum);

        int count = 0;
        int len = nums.Length;

        for (int i = 0; i < len - 2; i++)
        {
            for (int j = i + 1; j < len - 1; j++)
            {
                for (int k = j + 1; k < len; k++)
                {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (isPrime[sum])
                        count++;
                }
            }
        }

        return count;
    }
}

🔄 정리

기존에 sprt로 구하는 방법은 알아두었던터라 이번에 에라토스테네스라는 방식이 있는 것을 공부해두면 좋을 듯 하다