프로그래머스 - 소수 찾기

소수를 찾는 것은 쉬우나, 문자열을 입력받아 해당 문자들로 만들 수 있는 모든 수의 조합을 찾는 것을 재귀로 짜보려했으나 잘 되지 않았다. 그래서 next_permutation을 사용했다.

 

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> m;
int answer;
int find(int num)
{
    if (num < 2)
        return (0);
    if (num == 2 || num == 3)
        return (1);
    int i = 2;
    while (i * i <= num)
    {
        if (num % i == 0)
            return (0);
        i++;   
    }
    return (1);
}
 
int solution(string numbers) {
    int len = numbers.size();
    vector<bool> pv(numbers.size(), false);
    for(int i = 1; i <= len; i++){
        std::fill(pv.begin(), pv.end(), false);
        std::fill(pv.end() - i, pv.end(), true);
        do{
            string tmp;
            for(size_t j = 0; j < len; j++){
                if(pv[j]){
                    tmp += numbers[j];
                }
            }
            sort(tmp.begin(), tmp.end());
            do{
                int num = stoi(tmp);
                if(find(num) && !m[num])
                {
                    answer++;
                    m[num]++;
                }
            }while(next_permutation(tmp.begin(), tmp.end()));
        }while(next_permutation(pv.begin(), pv.end()));
    }
    return answer;
}