[코딩테스트] 소수 만들기 | 프로그래머스

문제

✍🏻 문제 바로가기

문제	레벨	정답률
소수 만들기	Lv.1	62%

My Code

class Solution {
    public int solution(int[] nums) {
        int result = 0;
        boolean distinction = false;
        
        for(int i = 0; i<nums.length-2; i++){
            for(int j = i+1; j<nums.length-1; j++){
                for(int p = j+1; p<nums.length; p++){
                    int num = nums[i] + nums[j] + nums[p];
                    
                    distinction = isPrime(num);
                    if(distinction == true){result++;}
                }
            }
        }
        
        return result;
    }
    
    
    public boolean isPrime(int num){
        if(num < 2){return false;}
        
        for(int i = 2; i<num; i++){
            if(num%i == 0){return false;}
        }
        
        return true;
    }
}

for문을 세 개 사용하여 전체 배열을 돌며 3가지 숫자를 pick했다.
그리고 소수인지 판별은 클래스로 빼서, 2부터 해당 숫자 전까지 돌면서 나머지가 0이면 false를 return하도록 하였다.

최적화 코드

class Solution {
    public int solution(int[] nums) {
        int result = 0;
        
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int p = j + 1; p < nums.length; p++) {
                    int num = nums[i] + nums[j] + nums[p];
                    
                    if (isPrime(num)) {
                        result++;
                    }
                }
            }
        }
        
        return result;
    }
    
    public boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

그런데 사실 소수를 판별할 때, 2부터 해당 숫자 전까지 전부 돌 필요는 없었다.
숫자의 제곱근까지만 확인하면 충분하다.

제곱근 구하기

Math.sqrt(num)

그 이유는 보통 약수를 전부 구해보면 제곱근을 기준으로 대칭을 이룬다. 그렇기 때문에 제곱근 이하의 숫자에서 나누어 떨어지는 약수가 없다면, 제곱근 이상에서도 없다는 의미가 된다.

---

쉬운 문제였지만, 그럼에도 내 코드가 최적화된 코드가 아니라면 충분히 풀 가치가 있다고 생각한다.
앞으로 소수 판별 문제가 나오면 더욱 효율적인 코드를 작성할 수 있게 되었으니 만족한다.