C++:: 프로그래머스 < 소수 찾기 >

주어진 숫자들을 조합하여 소수를 만들수 있다면 그 개수를 찾아서 리턴해주는 문제이다. dfs방식을 사용하여 완전 탐색을 하였다. 크게 어렵지는 않지만 조금 헤맬수도 있는 문제인것 같다.

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

vector<bool> era(10000000, true);//에라토스테네스의 체
vector<bool> vis(7, false);//방문 배열
int answer = 0, n;

void dfs(string ing, string numbers)
{
    if(ing.size() > 0 && era[stoi(ing)])
    {//만들어진 문자열을 정수형으로 변환한값이 소수이면
        era[stoi(ing)] = false;//중복되는 소수가 등장할 수 있으므로
        answer++;
    }
    for (int i=0;i<n;i++)
    {
        if (!vis[i])
        {
            string tmp = ing + numbers[i];//기존 숫자열 + 아직 안쓴 숫자
            vis[i] = true;
            dfs(tmp, numbers);
            vis[i] = false;
        }
    }
}

int solution(string numbers)
{
    
    n = numbers.size();
    for (int i=2;i*i<10000000;i++)//에라토스테네스의 체
        if (era[i])
            for (int j= i*i;j<10000000;j+=i) era[j] = false;
    era[0] = false; era[1] = false;//0 1 은 소수가 아니므로 
    dfs("", numbers);
    return answer;
}