Summer/Winter Coding(~2018) > 소수 만들기 - Level 1

 

안녕하세요 besforyou입니다

 

이번 글에서는 프로그래머스 문제 소수 만들기 문제를 설명해보겠습니다

 

주어진 숫자가 소수인지 아닌지를 빠르게 판별하는 방법을 알게 된 좋은 문제였습니다.

---

문제 풀이

 

3개의 과정을 거쳐 문제를 해결할 수 있습니다.

 

1. 주어진 배열 nums에서 3개의 숫자를 골라 더한 값을 배열에 저장한다.
2. 배열에 저장된 값을 하나씩 순차적으로 참조하여 소수인지 판별한다.
3. 찾은 소수의 개수를 반환한다.

 

 

1. 주어진 배열 num에서 3개의 숫자를 골라서 더한 후 배열에 저장

 

int len = nums.length;

 

 

2. 숫자가 소수인지 판별하는 함수 is_prime

 

이 문제의 핵심

 

3. 찾은 소수의 개수 반환

 

 

---

코드

 

import java.util.ArrayList;
 
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int len = nums.length;
 
        ArrayList<Integer> arr = new ArrayList<>();
 
        for ( int i = 0 ; i < len - 2 ; i++) {
            for ( int j = i + 1 ; j < len - 1 ; j++ ) {
                for ( int k = j + 1 ; k < len ; k++ ) {
                    arr.add( nums[i] + nums[j] + nums[k]);
                }
            }
        }
 
        for ( int i = 0 ; i < arr.size() ; i++ ) answer += is_prime(arr.get(i));
        return answer;
    }
 
    public int is_prime(int number) { // 소수가 아니면 0, 소수면 1 반환
 
        if(number < 2) return 0; // 0 또는 1은 소수가 아니다
 
        if(number == 2) return 1; // 2는 소수
 
        // 자기자신의 루트까지 자신을 나누었을때 나누어 떨어지면 소수가 아님
        // 나누어 떨어지지 않으면 소수. 시간복잡도를 O(N)에서 O(sqrt(N))까지 떨어뜨린다
        for(int i = 2; i <= Math.sqrt(number); i++) { 
            if(number % i == 0) return 0;
        }
 
        return 1;
    }
}
 

 

 

 

 

도움이 되셨으면 좋겠습니다.