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

문제 설명

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

 

제한사항

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

---

문제 파악

정수 배열 nums에서 서로 다른 3개의 수를 골라 합을 구한 뒤, 그 합이 소수인 경우의 수를 구하는 문제다.

 

접근 방법

• 중복 없이 3개의 수를 선택한다. -> for문
• 3개의 수의 합이 소수인지 판별한다. -> 2부터 루트x까지 나누어 떨어지는 수가 있는지 확인한다.

 

코드 구현

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int sum = 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++){
                    sum = nums[i] + nums[j] + nums[k];
                    int x = 0;
                    for(x=2; x<= Math.sqrt(sum); x++){
                        if (sum%x == 0 ) break;
                    }
                    
                    if(x > Math.sqrt(sum)) {
                        answer += 1;
                        System.out.println(nums[i] +","+ nums[j]+","+ nums[k]+"를 이용해서"+ sum + "을 만들 수 있습니다.");
                    }
                }
            }
        }
        return answer;
        }
    }

 

• for(x=2; x <= sqrt(sum); x++)로 소수 판별을 최적화했다.
• x > sqrt(sum)이면 약수가 없었다는 뜻이므로 소수라는 뜻이다.

 

 

다른 풀이 / 피드백

[정답 코드] 1) 완전탐색(개선)

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int counter = 0;
        //✅ nums에서 숫자 세개를 고른다. 
        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++) {
                //✅ 세 숫자의 합이 소수라면 카운터를 1 증가시킨다.
                    if (isPrime(nums[i] + nums[j] + nums[k])) counter++;
                }
            }
        }
        
        return counter;
    }
    
    //✅ 2 ~ i * i == n 까지 숫자로 n을 나누어본다. 나누어 떨어진다면 소수로 판별한다.
    private boolean isPrime(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

• 소수 판별을 함수로 분리해서 더 깔끔하다.

 

[정답 코드] 2) 에라토스 테네스의 체

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int count = 0;
        int maxSum = 2997;  // 최대 합은 1000 + 999 + 998 = 2997
        //✅ 에라토스 테네스의 체를 생성한다.
        boolean[] isPrime = sieveOfEratosthenes(maxSum);
        
        //✅ nums에서 숫자 세개를 고른다. 
        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];
                    //✅ 세 숫자의 합이 소수라면 카운터를 1 증가시킨다.
                    if (isPrime[sum]) count++;
                }
            }
        }
        
        return count;
    }

    private boolean[] sieveOfEratosthenes(int max) {
        boolean[] isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;  // 0과 1은 소수가 아님

	        for (int i = 2; i * i <= max; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        return isPrime;
    }
}

• 모든 소수를 미리 구해놓고 배열로 판별하므로 빠르다.
• 입력이 클수록 효과가 좋다.

 

배운 점

• 입력 범위를 고려한 알고리즘 선택
  → 1부터 1000까지인 숫자 범위라면, 세 수를 선택하는 3중 반복문을 사용해도 시간 초과가 발생하지 않겠다고 예측하고 사용할 수 있다.
• 3중 반복문으로 조합 생성 시 중복 제거
  → i, j, k의 시작 범위를 조절하여 중복을 피할 수 있다.

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++)

• 소수 판별 로직은 함수로 분리하여 재사용성 향상
  → isPrime(int num) 같은 함수로 분리하면 코드가 더 읽기 쉽고 관리도 용이하다.
• 에라토스테네스의 체를 활용한 소수 미리 계산
  → 반복적으로 소수 판별을 수행하는 대신, 미리 소수를 구해놓고 배열로 확인하면 성능이 크게 향상된다.