🔗 소수 만들기

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

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

입출력 예 #1

[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2

[1,2,4]를 이용해서 7을 만들 수 있습니다.

[1,4,6]을 이용해서 11을 만들 수 있습니다.

[2,4,7]을 이용해서 13을 만들 수 있습니다.

[4,6,7]을 이용해서 17을 만들 수 있습니다.

배열에서 임의의 요소 3가지를 선택하여 해당 수의 합이 소수가 되는 경우의 수를 구하는 문제.

1. 임의의 요소 3가지 선택
2. 요소의 합의 소수 여부 판별

이 두 로직을 구현하는 것이 알고리즘의 핵심이다.

보통 조합을 이용하지만, 간단하게 중첩 for문을 사용해 구현해보자.

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

임의의 세 가지 요소는 이와 같이 3중첩 for문을 통해 구할 수 있다. j, k의 인덱스를 유심히 살펴보자. 각 인덱스가 겹치지 않게끔 초기값이 구성되어있다.

JAVA
private boolean isPrime(int num)
{
	for (int i = 2; i <= Math.sqrt(num); i++)
	{
		// 나눠 떨어질 경우
		if (num % i == 0)
		{
			return false;
		}
	}
	
	return true;
}

소수는 이와 같이 구할 수 있다. 굳이 Math.sqrt(num) 까지만 연산히는 이유는, 제곱근 이후로는 연산할 필요가 없다.

예를 들어, 12의 경우 1, 2, 3, 4, 6, 12의 약수를 가지는데, $\sqrt{12}$는 대략 3이다. 3 이후의 숫자인 4, 6은 각각 2와 3과 곱해져서 12를 만들게 되므로, 제곱근 이전에 나누어 떨어지는 수가 없다면 그 수는 소수라 봐도 무방하다.

JAVA
/**
 * 소수 만들기 클래스
 *
 * @author RWB
 * @since 2021.12.10 Fri 00:21:09
 */
class Solution
{
	/**
	 * 해답 반환 메서드
	 *
	 * @param nums: [int[]] 숫자 배열
	 *
	 * @return [int] 소수가 되는 경우의 수
	 */
	public int solution(int[] nums)
	{
		int answer = 0;
		
		for (int i = 0; i < nums.length; i++)
		{
			for (int j = i + 1; j < nums.length; j++)
			{
				for (int k = j + 1; k < nums.length; k++)
				{
					int sum = nums[i] + nums[j] + nums[k];
					
					answer += isPrime(sum) ? 1 : 0;
				}
			}
		}
		
		return answer;
	}
	
	/**
	 * 소수 여부 반환 메서드
	 *
	 * @param num: [int] 숫자
	 *
	 * @return [boolean] 소수 여부
	 */
	private boolean isPrime(int num)
	{
		for (int i = 2; i <= Math.sqrt(num); i++)
		{
			// 나눠 떨어질 경우
			if (num % i == 0)
			{
				return false;
			}
		}
		
		return true;
	}
}