프로그래머스 Lv.1 - 12921 소수 찾기

프로그래머스 Lv.1 - 12921 소수 찾기 문제 풀이

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

문제의 자세한 내용은 해당 링크를 통해 확인 : 문제 링크

 

풀이 코드

import java.lang.Math;
import java.util.Arrays;

class Solution {
    /**
    에라스토테네스의 체 방식의 구현
    정확도 테스트
        테스트 1 〉	통과 (0.80ms, 79.3MB)
        테스트 2 〉	통과 (0.87ms, 76.8MB)
        테스트 3 〉	통과 (0.95ms, 79MB)
        테스트 4 〉	통과 (0.99ms, 67.6MB)
        테스트 5 〉	통과 (0.97ms, 75.1MB)
        테스트 6 〉	통과 (1.80ms, 77.6MB)
        테스트 7 〉	통과 (1.43ms, 75.3MB)
        테스트 8 〉	통과 (1.64ms, 76.1MB)
        테스트 9 〉	통과 (1.89ms, 77.4MB)
        테스트 10 〉	통과 (13.45ms, 77.3MB)
        테스트 11 〉	통과 (22.96ms, 79MB)
        테스트 12 〉	통과 (13.85ms, 85.1MB)
    효율성 테스트
        테스트 1 〉	통과 (28.28ms, 55.6MB)
        테스트 2 〉	통과 (68.43ms, 63.4MB)
        테스트 3 〉	통과 (61.96ms, 74.6MB)
        테스트 4 〉	통과 (38.48ms, 55.2MB)
    **/
    public int solution(int n) {
        double sqrt = Math.sqrt(n);
        int[] nArray = new int[n - 1];
        Arrays.fill(nArray, 0);
        
        for(int i = 0; i < sqrt && i < nArray.length; i++) {
            if(nArray[i] == 0) {
                int index = i + 2;
                for(int j = 2; index * j < nArray.length + 2; j++) {
                    nArray[(index * j) - 2] = 1;
                }
            }
        }
        return (int)Arrays.stream(nArray).filter(i -> i == 0).count();
    }

처음 구현했던 코드

import java.lang.Math;
import java.util.Arrays;

class Solution {
    /**
    3부터 입력 받은 n까지 순회하며 소수인지 판단하는 방식의 구현
    정확성 테스트
        테스트 1 〉	통과 (0.01ms, 79.9MB)
        테스트 2 〉	통과 (0.05ms, 75MB)
        테스트 3 〉	통과 (0.13ms, 76.3MB)
        테스트 4 〉	통과 (0.18ms, 76.2MB)
        테스트 5 〉	통과 (0.12ms, 72MB)
        테스트 6 〉	통과 (1.38ms, 78.3MB)
        테스트 7 〉	통과 (0.45ms, 77MB)
        테스트 8 〉	통과 (1.05ms, 81.7MB)
        테스트 9 〉	통과 (1.10ms, 72.9MB)
        테스트 10 〉	통과 (41.90ms, 87.6MB)
        테스트 11 〉	통과 (190.70ms, 102MB)
        테스트 12 〉	통과 (60.69ms, 77.5MB)
    효율성 테스트
        테스트 1 〉	통과 (205.39ms, 52.5MB)
        테스트 2 〉	통과 (202.02ms, 52.4MB)
        테스트 3 〉	통과 (216.21ms, 52.2MB)
        테스트 4 〉	통과 (186.38ms, 52.1MB)
    **/
    public int solution(int n) {
        int answer = 1;
        for(int i = 3; i <= n; i++) {
            if(isPrimeNumber(i)) {
                answer += 1;
            }
        }
        return answer;
    }
    
    public boolean isPrimeNumber(int n) {
        double sqrt = Math.sqrt(n);
        for(int i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

문제 해결 전략

이라 쓰고 문제를 보고서 어떻게 풀면 될까?에 대한 생각을 정리한 항목

처음에는 그냥 3부터(n의 입력 최소 범위는 2, 2는 항상 소수이기에 제외) 입력 받은 n까지 소수인지 판별하여 count를 올려서 반환하도록 구현하여 통과를 하긴 했지만..

효율성 테스트에서 200ms를 넘기는 것을 보고는 좀 더 효율적인 알고리즘이 없을까? 하고서 찾아보니 에라스토테네스의 체 방식을 알게 되었고, 이를 이용하면 좀 더 효율적으로 구현할 수 있을 것 같아서 구현을 해보니 최대 60ms의 동작 속도가 나오는 코드가 되었다.

그런데 전체적인 동작 속도를 비교해보니.. 입력 받은 n값이 작은 경우에는 첫 번째 구현 방법(입력 받은 n까지 전부 소수인지 판별하는 방식)이 좀 더 효율이 높게 나왔고, 어느정도 큰 수가 들어온 경우에는 두 번째 구현 방법(에라스토테네스의 체 방식)이 좀 더 효율이 높게 나왔다.

최고 효율을 뽑기 위해서는 에라스토테네스의 체 방식의 효율이 더 좋아지는 수를 찾은 후, 해당 수를 기준으로 나눠서 동작하도록 하는게 가장 좋을 것 같다고 생각하지만.. 둘 다 정상적으로 통과를 했기 때문에 일단 여기서 마무리 했습니다.

---

코드를 업로드해 둔 깃 허브