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

 

 

❤️ 문제설명

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

 

💛 제한사항

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

 

💚 출력 예시

​

💜 풀이

 

첫번째 시도 🙅🏻‍♀️ - 틀림

class Solution {
    public int solution(int[] nums) {
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; k < nums.length; k++) {
                    int num = nums[i] + nums[j] + nums[k];
                    if (isPrime(num)) count++;
                }
            }
        }
        return count;
    }
    public boolean isPrime(int num) {
        if (num == 2) return true;
        for ? // 여기서 소수 판별하는 코드를 어떻게 짜야 하는지 모르겠다
    }
}

 

일단 소수 판별 메서드 만드는 방법을 찾아보았다.

소수는 1과 자기 자신으로만 나누어 떨어지는 정수를 말하는데,

수학적으로는 숫자 num이 소수인지 확인하기 위해 모든 수를 나눌 필요 없이, num의 제곱근까지만 확인하면 됨.

 

예를 들어서, 36의 약수들은 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)과 같이 짝을 이루기 때문에,

약수 중 제곱근 이하만 확인해도 전체 약수를 알 수 있다. 왜나하면 제곱근 이상은 어차피 앞뒤 숫자만 바뀐 조합이기 때문

그래서 num이 소수라면, 제곱근 이하의 수들 중 num을 나누어떨어지게 하는 수가 없어야 한다.

 

 

일단 num이 1이면 소수가 아니다. 

for 반복문에서 i는 2부터 시작하여 Math.sqrt(num)까지 증가하며, num을 i로 나누었을 때 나머지가 0인지 확인해야 한다.

만약 num % i == 0이라면, num이 i로 나누어떨어진다는 뜻이므로, 소수가 아니라는 뜻.

 

 

 

public boolean isPrime(int num) {
    if (num <= 1) return false; // 1 이하의 숫자는 소수가 아님
    for (int i = 2; i <= (int) Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false; // 나누어떨어지는 수가 있으면 소수가 아님
        }
    }
    return true; // 소수인 경우
}

 

두번째 시도 🙅🏻‍♀️ - 틀림

또 틀림

class Solution {
    public int solution(int[] nums) {
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; k < nums.length; k++) {
                    int num = nums[i] + nums[j] + nums[k];
                    if (isPrime(num)) count++;
                }
            }
        }
        return count;
    }
    
    public boolean isPrime(int num) {
        if (num <= 1) return false; 
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false; 
            }
        }
        return true; 
    }
}

 

 

 

 

- isPrime 메서드 아래처럼 수정해 보기로 함.

num이 1 인경우, 2인 경우, 그 이상인 경우 나누어서 수행 

1은 포함 안되고, 2는 소수이고, 3부터는 포문 돌려야 하기 때문

 public boolean isPrime(int num) {
        if (num <= 1) return false; // 1 이하의 숫자는 소수가 아님
        if (num == 2) return true; // 2는 소수
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false; // 나누어 떨어지면 소수가 아님
            }
        }
        return true; // 소수인 경우
    }

 

 

- 3중 포문의  인덱스 문제

 

- i는 0부터 시작해서 nums.length - 2까지만 반복함. i는 첫 번째 숫자의 인덱스이므로 뒤에 두 개의 숫자를 추가로 선택할 수 있어야 함. 따라서, nums.length - 2까지만 반복하게 됨

 

- j는 i + 1부터 시작 nums.length - 1까지만 반복. 이렇게 해야 j가 i와 중복안됨. j는 두 번째 숫자의 인덱스이므로, i 다음 위치에서 시작해야 하고, 뒤에 세 번째 숫자 k를 선택할 수 있어야 하므로 nums.length - 1까지만 반복해야 함.

 

- k는 j + 1부터 시작하여 nums.length까지 반복. k는 세 번째 숫자의 인덱스이므로, j 다음 위치에서 시작해야 함

이렇게 해야 i, j, k 세 개의 숫자를 반복하지 않고 조합을 탐색할 수 있음. 

 

 

 

public int solution(int[] nums) {
    int count = 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 num = nums[i] + nums[j] + nums[k];
                if (isPrime(num)) count++;
            }
        }
    }
    return count;
}

 

 

세번째 시도 🙆‍♀️ - 정답🥳

class Solution {
    public int solution(int[] nums) {
        int count = 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 num = nums[i] + nums[j] + nums[k];
                    if (isPrime(num)) count++;
                }
            }
        }
        return count;
    }
    
    public boolean isPrime(int num) {
        if (num <= 1) return false; // 1 이하의 숫자는 소수가 아님
        if (num == 2) return true; // 2는 소수
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false; // 나누어 떨어지면 소수가 아님
            }
        }
        return true; // 소수인 경우
    }
}