[알고리즘] 프로그래머스 : 소수 찾기

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

---

내가 작성한 코드(효율성 때문에 여러번 코드를 짰던 문제)

좀처럼 풀이가 생각이 안나서 일단 반복문으로 돌렸다. 자기자신과 같지 않은 수로 나누었을 때 나누어떨어지는 수를 구한 후 집계하고 조금이라도 속도를 빠르게 하기 위해 바로 반복문을 break 시켰다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int aliquot = 0;
        for(int i=2; i<=n; i++){
            for(int j=2; j<=i/2; j++){
                if(i!=j && i%j==0){
                    aliquot+=1;
                    break;
                }
            }
        }
        answer = (n-1) - aliquot; //1을 제외한 소수
        return answer;
    }
}

하지만 예상대로 효율성 실패...

 

그래서 2가 아닌 짝수인 경우에는 어차피 소수가 아닐테니, 미리 소수가 아닌 수에 집계해놓고 짝수가 나오면 continue를 해서 조금이라서 반복문 횟수를 줄였다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int aliquot = n/2-1; //2를 제외한 짝수의 개수
        for(int i=2; i<=n; i++){
            if(i%2==0) continue;
            for(int j=3; j<=i/2; j++){
                if(j%2==0) continue;
                if(i!=j && i%j==0){
                    aliquot+=1;
                    break;
                }
            }
        }
        answer = (n-1) - aliquot; //1을 제외한 소수
        return answer;
    }
}

속도가 미세하게 올라가긴 했지만 역시 효율성 실패...ㅜㅜ

 

생각해보니 약수를 구할 때 정중앙에 오는 것은 해당되는 수의 절반이 아니라 해당되는 수의 제곱근이다. 그래서 위의 코드를 그대로 쓰되 Math.sqrt() 메소드를 써서 j를 n의 제곱근까지만 돌게 해서 반복횟수를 크게 줄였더니 통과했다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int aliquot = n/2-1; //2를 제외한 짝수의 개수
        for(int i=2; i<=n; i++){
            if(i%2==0) continue;
            for(int j=3; j<=(int)Math.sqrt(n); j++){
                if(j%2==0) continue;
                if(i!=j && i%j==0){
                    aliquot+=1;
                    break;
                }
            }
        }
        answer = (n-1) - aliquot; //1을 제외한 소수
        return answer;
    }
}

와... 테스트 12를 보면 4565.73ms나 걸리던 코드가 50.77ms로 확 줄었다. 이래서 알고리즘이 중요하구나.

 

그래도 200ms는 너무 긴 것 같아서 방법을 다시 고민해보았다.

에라토스테네스의 체( https://terms.naver.com/entry.nhn?docId=1179083&cid=40942&categoryId=32204 )라는 게 있다. 사실 나도 이 생각을 하긴 했었는데 공배수를 어떻게 처리할지 고민이 되어 시도하지 못했었다. 하지만 이 방법으로 풀 수 있는 문제라고 해서 나도 이 방식으로 풀어보기로 했다.

 

0과 1과 합성수를 담을 배열 notPrime을  n+1의 크기로 만든다. 이 배열에는 0~n까지의 인덱스가 있을 것이다. boolean 타입의 배열이므로 디폴트값은 모두 false이다.(여기에서 0번째, 1번째를 true로 바꿀 수도 있지만 어차피 나는 2번째 인덱스부터 반복문을 돌릴 예정이라서 굳이 바꾸지 않았다.)

이제 2의 배수, 3의 배수, 4의 배수,..., k의 배수를 구할 것이다. k는 2부터 출발하며 k*k가 n보다 커서는 안 된다는 반복문 조건을 미리 정해준다. 그리고 2배, 3배, 4배, ..., j배를 해줄 건데 이 때 k*j 또한 n보다 커서 안 되므로 안에 있는 반복문에도 조건을 미리 정해준다. 그 뒤 i*j 인덱스의 값이 true일 경우 이미 한번 구한 값이므로 continue로 지나가게 하고, 그게 아니라면 true를 저장하게 한다. 

이제 2부터 n까지 인덱스를 넣어서 false인 값만 뽑아내고 그 때마다 answer의 숫자를 증가시키면 된다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] notPrime = new boolean[n+1];
        for(int i=2; i*i<=n; i++){
            for(int j=2; i*j<=n; j++){
                if(notPrime[i*j]==true) continue;
                notPrime[i*j]=true;
            }
        }
        for(int i=2; i<n+1; i++){
            if(notPrime[i]==false) answer++;
        }
        return answer;
    }
}

약 200ms였던 효율성이 약 10ms로 거의 1/20이 줄었다!