소수만들기

문제 설명

주어진 숫자 중 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개씩 고른 모든 경우의 수

시간 복잡도를 최대한 줄이고 싶어서 이중 포문으로 작성했지만 3중 포문밖에 답을 못구할 거 같에서 아래와 같이 작성했다.

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

소수 구하는 알고리즘

    public boolean isprime(int num)
    {
        for(int i = 2; i < num; i++)
        {
            if( num % i == 0)
                return false; // 소수
        }
        return true; // 소수 아님
    } 

소수는 자기자신과 1 이외에는 어떠한 정수든 나뉘어 떨어지지 않는 수이기 때문에 위와 같이 작성을 했다.

코드

class Solution {
    public int solution(int[] nums) {
        
        int cnt = 0;
        for(int i = 0 ; i < nums.length-2; i++)
        {
            
            for(int j = i+1 ; j < nums.length-1; j++)
            {
                for(int k = j+1; k < nums.length; k++)
                {
                     int sum = nums[i] + nums[j] + nums[k];
                     if (isprime(sum) == true)
                          cnt++;
                }
               
            }
        }
        return cnt;
    }
    
    public boolean isprime(int num)
    {
        for(int i = 2; i < num; i++)
        {
            if( num % i == 0)
                return false; // 소수아님
        }
        return true; // 소수
    }
}

느낀점

그렇게 어렵지 않은 난이도 인데도 불구하고 소수 개념에서 살짝 헷갈려서 시간이 걸린게 아쉽다.
지금이라도 개념을 확실히 잡아서 다행이다!! 😋