[프로그래머스] 소수 만들기 - 자바(Java)

문제 링크

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

코딩테스트 연습 - 소수 만들기

 

 

문제 설명

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

 

 

제한사항

• 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을 만들 수 있습니다.

 

 

코드

class Solution {
    public int solution(int[] nums) {
    	// 소수의 개수를 세기 위한 count 선언
        int count = 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 num = nums[i] + nums[j] + nums[k];
                    // 소수 판별 후 count 증가
                    if (isPrime(num)) count += 1;
                }
            }
        }

        return count;
    }
    
    // 소수 판별 메서드
    private boolean isPrime(int num) {
        if (num == 2) return true;
        
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

코드 설명

주석 참고

• nums 배열에 존재하는 수 중 세 가지 수를 합하여 해당 값이 소수인지 판별하고, 소수이면 1씩 증가시켜 소수가 되는 경우의 개수를 구하는 문제다.
• nums 배열에 존재하는 세 가지 수를 합하는 경우의 수는 3개의 중첩 for 문을 이용한다.
• 모든 경우의 수를 찾는 것이 아니므로 첫 번째 for 문의 i는 0부터, 두 번째 for 문의 j는 i + 1, 세 번째 for 문의 k는 j + 1부터 순회한다.(순열과 조합에서의 조합)
• 세 번째 for 문 안에 세 가지 수의 합(nums[i] + nums[j] + nums[k])을 구하여 소수인지 판별한다.
• 소수인지 판별하는 isPrime() 메서드는 세 가지 수의 합인 num을 입력받아 num이 소수이면 true, 소수가 아니면 false를 반환한다.
• 숫자 2는 소수로 취급하므로 2인 경우 true를 반환하고, 이 외의 수는 반복문을 통해 판별한다.
• i는 2부터 num의 제곱근까지 반복하여 num을 i로 나눈 나머지가 0인 경우 false를 반환한다.
• 반복문을 무사히 마치면 소수이므로 true를 반환한다.