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

문제

링크

코딩테스트 연습 > Summer/Winter Coding(~2018) > 소수 만들기 (Lv. 1)
정답률 61% (2023.05.14 기준)

 

문제 설명

주어진 숫자 중 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을 만들 수 있습니다.

 

풀이

완전탐색 및 소수 판별 알고리즘을 이용한 문제이다. 세 가지 수를 더해 나올 수 있는 값의 모든 경우의 수에서 소수가 되는 경우의 개수를 구하면 된다. 

소수를 구하는 메소드는 따로 빼서 호출할 것인데, 데이터의 크기가 크지 않아서 단순한 소수 판별 알고리즘을 사용해도 무리 없이 통과하지만, 에라토스테네스의 체를 사용하는 방식도 같이 적어보려 한다.

 

코드

class Solution {
    public int solution(int[] nums) {
        int answer = 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++) {
                    if(isPrime(nums[i]+nums[j]+nums[k])) answer++;
                }
            }
        }
        return answer;
    }
    
    // 소수 판별 - 단순
    private boolean isPrime(int number) {
        if(number < 2) return false;
        for(int i=2;i<Math.sqrt(number);i++) {
            if(number%i==0) return false;
        }
        
        return true;
    }
    
    // 소수 판별 - 에라토스테네스의 체
    private boolean isPrime2(int number) {
        if(number < 2) return false;
        boolean[] primes = new boolean[number+1];
        
        for(int i=0; i<primes.length; i++){
            primes[i] = true; // 배열을 true로 초기화
        }
        primes[0] = primes[1] = false; // 0, 1
        
        for(int i=2; i<=Math.sqrt(number); i++){
            if(primes[i]){ // 소수면 해당 수를 제외 모든 배수 false
                for(int j = i*i; j<= number; j += i){
                    primes[j] = false;
                }
            }
        }
        return primes[number];
    }
}

 

해결 과정

1. 숫자가 소수인지 판별하는 isPrime 메소드를 만든다.
   
   • 1은 소수가 아니기 때문에 2보다 작은 경우는 false를 리턴한다. (세 가지 숫자의 합은 무조건 3 이상이므로 이 문제에서는 이 조건은 제외시켜도 될 듯하다.)
   • 2부터 해당 숫자의 제곱근까지 i를 1씩 차례로 증가시키면서, number가 i로 나누어 떨어지면 소수가 아니기 때문에 false를 리턴한다.
   • 이외의 경우 소수이므로 true를 리턴한다.
2. solution 메소드에서 서로 다른 3개의 수의 합의 경우의 수를 모두 구해, 해당 수가 소수라면 answer에 1을 더해준다.
   
   • 3중 for문을 사용하였고, 반복 범위에 주의하도록 한다.
3. 최종적으로 구해진 answer를 정답으로 return한다.

 

에라토스테네스의 체 Sieve of Eratosthenes

문제 해결에 사용한 방식 외에도 에라토스테네스의 체를 이용해 어떠한 숫자가 소수인지 판별할 수 있다.

문제에서는 자신보다 작은 숫자들 중 어떠한 숫자로 자신이 나누어 떨어지면, 자신이 해당 숫자의 배수라는 점을 이용해 소수를 판별하였다. 하지만, 이 방식은 숫자가 100만 이상으로 커지면 시간초과로 풀이에 실패할 것이다.

이렇게 숫자가 커지면 에라토스테네스의 체 방식을 사용한다. 에라토스테네스의 체는 대표적인 소수 판별법으로, 아래 이미지를 보면 원리를 이해하기 쉽다. (이미지 출처: 위키백과)

 

 

위의 코드에 작성한 isPrime2 함수에서는 다음의 과정으로 소수 여부를 구한다. 

1. 주어진 범위까지 배열을 생성한 후 모든 값을 true로 초기화한다.
   • 예를 들어, 숫자가 100이라면 배열의 인덱스가 0부터 시작된다는 점을 고려하여 100 + 1 크기의 배열을 생성한다.
   • 배열의 n번째 요소는 해당 인덱스값 숫자의 소수 여부를 나타낸다.
2. 0과 1은 소수가 아니므로 false 값을 넣어 준다.
3. 2부터 number의 제곱근까지 탐색해서, 해당 값이 true면, 즉 소수면 해당 수를 제외한 모든 배수에 false값을 넣어 준다.
   • 해당 소수의 배수는 모두 소수가 아니기 때문이다.
   • number가 a*b라고 가정했을 때, a와 b 모두 number의 제곱근보다 클 수 없으므로 제곱근까지만 탐색해도 된다
4. 완성한 에라토스테네스의 체 배열에서 number번째 값을 return해 준다.

 

실행 결과