[Programmers/JAVA] 02. 소수 만들기

📄  소수 만들기

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

 

 

문제 분석

배열 nums 안의 숫자 중 서로 다른 3개의 수를 더했을 때, 소수가 되는 경우의 개수를 구하는 문제이다.

 

접근 방법

완전 탐색  을 이용하여 서로 다른 3개의 숫자를 선택하고 그 합이 소수가 되는 경우의 개수를 구한다.

 

주어진 숫자를 $N$, 배열 nums 의 크기를 $K$라고 할 때, 시간 복잡도는 $O(NK^{3})$이다.

$N = 3a$ 인 경우, $N$은 $I = 3$ 일 때와 $I = a$ 일 때 모두 $N$을 나누어 떨어지게 한다.

따라서 $I$는 $I^{2} = N$이 되는 경우까지 확인하면 되므로 시간 복잡도는 $O(\sqrt{N}K^{3})$이다.

 

코드 설계

solution 함수

# 소수의 개수를 저장할 변수 result, 세 숫자의 합을 저장할 변수 sum 을 선언한다.

# 3중 for 문을 수행하여 배열 안의 3개의 숫자의 합을 구한다.

# 서로 다른 3개의 숫자를 선택해야 하므로 이전 for 문보다 시작값을 1씩 증가시켜 실행한다.

# 세 숫자의 합 sum 을 isPrime 함수에 대입하여 true 값이 리턴되면 result 값을 1 증가시킨다.

# 모든 for 문을 반복한 후 result 값을 리턴한다.

 

isPrime 함수

# 숫자가 소수인지 아닌지를 판단하는 함수로 int 자료형의 sum 을 매개변수로 받고 리턴형이 boolean 이다.

# 소수 sum 은 1과 자신만을 약수로 갖는 수이므로 2부터 루트 sum 까지만 for 문을 수행한다.

# sum 을 1이 아닌 다른 수로 나누었을 때 나머지가 존재하지 않는다면 소수가 아니므로 false 를 반환한다.

# 반대로 나머지가 존재한다면 true 를 반환한다.

 

코드 구현

class Solution {
    public int solution(int[] nums) {
        int result = 0;
        int sum = 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++) {
                    sum = nums[i] + nums[j] + nums[k];
                    if(isPrime(sum) == true) result++;
                }
            }
        }
        
        return result;
    }
    
    public boolean isPrime(int sum) {
        for(int i=2; i*i<=sum; i++) {
            if(sum % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}