문제

풀이

우선 소수를 판별하는 것에는 에라토스테네스의 체를 사용했습니다. 에라토스테네스의 체는 이 포스팅 에서 자세히 다뤄보았습니다.
3가지 수를 합해서 나올 수 있는 모든 수들의 소수 체크를 해줘야 합니다. 그렇기 때문에 일정범위 안에 있는 수 들이 소수인지 아닌지 판별할 때 유리할거라 생각하여 에라토스테네스의 체 알고리즘을 사용했습니다. 다음은 에라토스테네스의 체를 구현한 함수입니다.

// 에라토스테네스의 체
void eratos(){
    for(int i=2;i<=MAX;i++)
        primeNum[i]=1;
    for(int i=2;i<=sqrt(MAX);i++){
        if(primeNum[i]==0)
            continue;
        for(int j=i*i;j<=MAX;j+=i)
            primeNum[j]=0;
    }
}

3개를 더하는 모든 조합을 찾을 때는 재귀함수를 사용했습니다.

// 3개를 더하는 모든 조합 찾기
void findPrimeNum(vector<int> &nums,int L,int index, int sum){
    if(L==3){
        // 합이 소수이면 cnt 1 증가
        if(primeNum[sum]) cnt++;
        return;
    }
    for(int i=index;i<nums.size();i++){
        findPrimeNum(nums,L+1,i+1,sum+nums[i]);
    }
}

그렇다면 제 생각처럼 에라토스테네스의 체가 이 문제에서 더 빨랐는지 확인해보겠습니다.

우선 에라토스테네스의 체를 사용한 제 코드의 결과입니다. 스크린샷 2020-12-23 오후 10 40 21 테스트 케이스의 크기에 상관없이 일정하게 0.2ms 속도를 보입니다.

다음은 프로그래머스에서 가장 좋아요를 많이 받은 코드의 결과입니다. 이 분은 while문을 사용하여 소수를 판별했습니다. 스크린샷 2020-12-23 오후 10 41 18 테스트 케이스가 작을때는 0.01ms 정도로 제 코드보다 빠르지만 테스트 케이스의 크기가 커지면 5ms 까지 느려지는 것을 확인할 수 있습니다.

결론적으로 에라토스테네스의 체는 판별해야 하는 소수의 개수들이 많아지면 많아질수록 유리한 알고리즘이고 만약 판별해야 하는 소수가 적다면 단순히 while문을 통해 소수판별을 구현하는 것이 더 효율적일 수도 있습니다.

코드

#include <vector>
#include <iostream>
#include <cmath>
#define MAX 50000
using namespace std;

int primeNum[MAX+1];
int cnt;
// 에라토스테네스의 체
void eratos(){
    for(int i=2;i<=MAX;i++)
        primeNum[i]=1;
    for(int i=2;i<=sqrt(MAX);i++){
        if(primeNum[i]==0)
            continue;
        for(int j=i*i;j<=MAX;j+=i)
            primeNum[j]=0;
    }
}

// 3개를 더하는 모든 조합 찾기
void findPrimeNum(vector<int> &nums,int L,int index, int sum){
    if(L==3){
        // 합이 소수이면 cnt 1 증가
        if(primeNum[sum]) cnt++;
        return;
    }
    for(int i=index;i<nums.size();i++){
        findPrimeNum(nums,L+1,i+1,sum+nums[i]);
    }
}

int solution(vector<int> nums) {
    eratos();
    findPrimeNum(nums,0,0,0);
    return cnt;
}

[프로그래머스] 소수 만들기- C++

level2, 에라토스테네스의 체

문제

풀이

코드

CATALOG

FEATURED TAGS