[C++] 프로그래머스 문제풀이 LEVEL 2 소수 찾기

 

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

프로그래머스

 

 

#include <bits/stdc++.h>
using namespace std;

set<int> Set;

bool isPrime(int n)
{
    if (n <= 1)
    {
        return false;
    }
    
    bool res = true;
    int lim = sqrt(n);
    for (int i = 2; i <= lim; ++i)
    {
        if (n % i == 0)
        {
            res = false;
            break;
        }
    }
    return res;
}

void recur(size_t depth, size_t targetdepth, string str, string notuse)
{
    if (str.length() != 0)
    {
        Set.emplace(stoi(str));
    }

    if (depth == targetdepth)
    {
        return;
    }
    
    
    for (int i = 0; i < notuse.length(); ++i)
    {
        recur(depth + 1, targetdepth, str += notuse[i], notuse.substr(0, i) + notuse.substr(i + 1));
        str.pop_back();
    }

}

int solution(string numbers)
{
    int answer = 0;
    recur(0, numbers.length(), "", numbers);

    for (auto iter = Set.begin(); iter != Set.end(); ++iter)
    {
        int num = *iter;
        if (isPrime(num))
        {
            ++answer;
        }
    }
    return answer;
}