시리즈 톺아보기

프로그래머스

소수 만들기

문제 설명
제한사항
입출력 예

입출력 예 설명

풀이
코드

소수 만들기 🔗

랭크	사용 언어
Level 1

🔗 소수 만들기

문제 설명 🔗

주어진 숫자 중 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

입출력 예 설명 🔗

입출력 예 #1

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

입출력 예 #2

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

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

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

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

풀이 🔗

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

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

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

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

JAVA

0 for (int i = 0; i < nums.length; i++)
1 {
2     for (int j = i + 1; j < nums.length; j++)
3     {
4         for (int k = j + 1; k < nums.length; k++)
5         {
6             int sum = nums[i] + nums[j] + nums[k];
7         }
8     }
9 }

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

JAVA

0 private boolean isPrime(int num)
1 {
2     for (int i = 2; i <= Math.sqrt(num); i++)
3     {
4         // 나눠 떨어질 경우
5         if (num % i == 0)
6         {
7             return false;
8         }
9     }
10     
11     return true;
12 }

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

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

코드 🔗

JAVA

0 /**
1  * 소수 만들기 클래스
2  *
3  * @author RWB
4  * @since 2021.12.10 Fri 00:21:09
5  */
6 class Solution
7 {
8     /**
9      * 해답 반환 메서드
10      *
11      * @param nums: [int[]] 숫자 배열
12      *
13      * @return [int] 소수가 되는 경우의 수
14      */
15     public int solution(int[] nums)
16     {
17         int answer = 0;
18         
19         for (int i = 0; i < nums.length; i++)
20         {
21             for (int j = i + 1; j < nums.length; j++)
22             {
23                 for (int k = j + 1; k < nums.length; k++)
24                 {
25                     int sum = nums[i] + nums[j] + nums[k];
26                     
27                     answer += isPrime(sum) ? 1 : 0;
28                 }
29             }
30         }
31         
32         return answer;
33     }
34     
35     /**
36      * 소수 여부 반환 메서드
37      *
38      * @param num: [int] 숫자
39      *
40      * @return [boolean] 소수 여부
41      */
42     private boolean isPrime(int num)
43     {
44         for (int i = 2; i <= Math.sqrt(num); i++)
45         {
46             // 나눠 떨어질 경우
47             if (num % i == 0)
48             {
49                 return false;
50             }
51         }
52         
53         return true;
54     }
55 }

📆 작성일

2021-12-14 Tue 10:06:57

📚 카테고리

알고리즘

🏷️ 태그

프로그래머스

알고리즘

JAVA(자바)

Level 1

[프로그래머스 / JAVA] Level 1 음양 더하기 (76501)

[프로그래머스 / JAVA] Level 1 완주하지 못한 선수 (42576)

𝝅번째 알파카의 개발 낙서장

[프로그래머스 / JAVA] Level 1 소수 만들기 (12977)

posts

알고리즘

시리즈 톺아보기

Table of Contents

소수 만들기 🔗

문제 설명 🔗

제한사항 🔗

입출력 예 🔗

입출력 예 설명 🔗

풀이 🔗

코드 🔗

0	for (int i = 0; i < nums.length; i++)
1	{
2	for (int j = i + 1; j < nums.length; j++)
3	{
4	for (int k = j + 1; k < nums.length; k++)
5	{
6	int sum = nums[i] + nums[j] + nums[k];
7	}
8	}
9	}

0	private boolean isPrime(int num)
1	{
2	for (int i = 2; i <= Math.sqrt(num); i++)
3	{
4	// 나눠 떨어질 경우
5	if (num % i == 0)
6	{
7	return false;
8	}
9	}
10
11	return true;
12	}

0	/**
1	* 소수 만들기 클래스
2	*
3	* @author RWB
4	* @since 2021.12.10 Fri 00:21:09
5	*/
6	class Solution
7	{
8	/**
9	* 해답 반환 메서드
10	*
11	* @param nums: [int[]] 숫자 배열
12	*
13	* @return [int] 소수가 되는 경우의 수
14	*/
15	public int solution(int[] nums)
16	{
17	int answer = 0;
18
19	for (int i = 0; i < nums.length; i++)
20	{
21	for (int j = i + 1; j < nums.length; j++)
22	{
23	for (int k = j + 1; k < nums.length; k++)
24	{
25	int sum = nums[i] + nums[j] + nums[k];
26
27	answer += isPrime(sum) ? 1 : 0;
28	}
29	}
30	}
31
32	return answer;
33	}
34
35	/**
36	* 소수 여부 반환 메서드
37	*
38	* @param num: [int] 숫자
39	*
40	* @return [boolean] 소수 여부
41	*/
42	private boolean isPrime(int num)
43	{
44	for (int i = 2; i <= Math.sqrt(num); i++)
45	{
46	// 나눠 떨어질 경우
47	if (num % i == 0)
48	{
49	return false;
50	}
51	}
52
53	return true;
54	}
55	}