[알고리즘C++]소수 찾기

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/42839#

소수 찾기

나의 풀이

#include <string>
#include <vector>
#include <set>

using namespace std;
string per;
set<int> perSet;
bool check[100] = { false, }; 
vector<char>num;

void permutation(int depth, int n){
    if(depth == n){
        perSet.insert(stoi(per));
        return;
    }
    for(int i = 0; i < num.size(); i++){
        if(!check[i]){
            check[i] = true;
            per[depth] = num[i];
            permutation(depth + 1, n);
            check[i] = false;
        }
    }
}
int solution(string numbers) {
    int answer = 0;
    for(int i=0;i<numbers.size();i++){ // 숫자 저장
        num.push_back(numbers[i]);
    }
    string temp_per ="00000000000000";
    for(int i=1;i<=numbers.size();i++){
        per = temp_per.substr(0, i);
        permutation(0, i);
    }
    set<int> ::iterator Iter_Pos = perSet.begin();  
    for(;Iter_Pos != perSet.end();Iter_Pos++){
        int sosu = *Iter_Pos;
        if(sosu == 2){
            answer ++;
            continue;
        }
        for(int i=2;i<sosu;i++){
            if(sosu%i == 0)
                break;
            if(i == sosu-1){
                answer++;}
        } 
    }
    return answer;
}

모범정답

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#define MAX 9999999999
using namespace std;

bool isPrime(int number)
{
    if (number == 1)
        return false;
    if (number == 2)
        return true;
    if (number % 2 == 0)
        return false;

    bool isPrime = true;
    for (int i = 2; i <= sqrt(number); i++)
    {
        if (number% i == 0)
            return false;
    }

    return isPrime;
}

bool compare(char a, char b)
{
    return a > b;
}

int solution(string numbers) {
    int answer = 0;

    string temp;
    temp = numbers;

    sort(temp.begin(), temp.end(),compare);

    vector<bool> prime(std::stoi(temp)+1);

    //cout << stoi(temp) << endl;
    prime[0] = false;
    for (long long i = 1; i < prime.size(); i++)
    {
        prime[i] = isPrime(i);
    }
    //cout << "chk1" << endl;
    //int num = std::stoi(numbers);

    string s, sub;

    s = numbers;

    sort(s.begin(), s.end());
    set<int> primes;
    int l = s.size();
    do {
        for (int i = 1; i <= l; i++)
        {
            sub = s.substr(0, i);
        //  cout << "chk2" <<  " " << sub<<  endl;
            if (prime[std::stoi(sub)])
            {
                primes.insert(std::stoi(sub));
            }
        }
    } while (next_permutation(s.begin(), s.end()));

    //cout << primes.size();
    answer = primes.size();
    return answer;
}

배울 점

• string 처리 방법에 대해 잘 공부하게 되었음
• 조합 알고리즘을 사용해 볼 수 있었다 재귀로 만들어 낼 수 있구나 알게됨