[프로그래머스] 소수 찾기 c++

문제

소수 찾기 프로그래머스 level2

리뷰

완전탐색 카테고리의 문제다.

에라토스테네스의 체로 소수를 체크해야 하고. 주어진 숫자들로 순열을 만들면 된다.

 

핵심 코드

bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

1. 예를 들어 71까지의 소수를 구하려면 72 크기의 배열을 만든다.소수의 배수들은 소수가 아니기 때문이다.
   에라토스테네스 GIF를 참고하자
2. 소수를 만날 때 마다 (인덱스 값이 true 라면, ) 소수의 배수가 되는 인덱스들의 값을 전부 false로 만든다.
3. 구하려는 범위 만큼 bool 배열을 만들고, 배열의 인덱스를 전부 소수라고 생각하여 true로 초기화 한다.

[C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체

 

순열 만들기오름차순으로 정렬되어 있다면, 예를 들어 대상 벡터가 [1, 2, 3] 이라면, [3, 2, 1] 이 될 때 까지 순열을 만들어서 리턴해준다.

2. 따라서 반드시 미리 오름차순 정렬이 되어 있어야 한다. [3, 2, 1] 인채로 넣으면 바로 종료된다.
3. #include <algorithm>
next_permutation(v.begin(), v.end())

코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;


bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

int solution(string numbers) {

    sort(numbers.begin(), numbers.end(), greater<int>()); 
    // 내림차순 정렬 -> 숫자로 만들 수 있는 가장 큰 수 만들기.

    int maxnum = atoi(numbers.c_str()); // 문자열->숫자

    eratos(maxnum); // 소수 체크

    sort(numbers.begin(), numbers.end()); // 오름차순 정렬 (next_permutation 함수 활용을 위함.)

    set<int> answer_set; // 유효한 숫자를 중복없이 저장하기 위한 set

    do{
        // substr로 1자리 숫자 부터 확인 
        for(int i = 1; i <= numbers.size(); i++){
            int temp_num = stoi( numbers.substr(0, i) );
            if(prime[temp_num]){
                answer_set.insert(temp_num); // set에 넣어서 중복제거 
            }
        } 

    }while( next_permutation(numbers.begin(), numbers.end()) ); 

    return answer_set.size();
}