소수 찾기 / 순열, DFS

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

numbers 문자열의 크기가 7 이하이므로 브루트포스로 문제를 해결하려고 했고, 연습삼아 next_permutation을 사용해 순열, 그리고 DFS로 두 번 풀이해보았다.
두 방법 모두, 모든 수의 조합을 시도하며 각 수가 소수인지 판단하여 unordered_set에 넣어 중복된 숫자를 제거하였다.

 

✅ 순열을 이용한 풀이

#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <algorithm>

using namespace std;

bool isprimenum(const string& str)
{
    int num = stoi(str);

    for (int i = 2; i <= sqrt(num); ++i)
    {
        if (num % i == 0) return false;
    }

    return true;
}

int solution(string numbers)
{
    unordered_set<int> prime_num;
    sort(numbers.begin(), numbers.end());

    do
    {
        for (int len = 1; len <= numbers.length(); ++len)
        {
            string str = numbers.substr(0, len);

            if (stoi(str) < 2) continue;

            if (prime_num.find(stoi(str)) == prime_num.end())
            {
                if (isprimenum(str)) prime_num.insert(stoi(str));
            }
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

    return prime_num.size();
}

 

✅ DFS를 이용한 풀이

#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>

using namespace std;

bool isprimenum(const string& str)
{
    int num = stoi(str);

    if (num < 2) return false;

    for (int i = 2; i <= sqrt(num); ++i)
    {
        if (num % i == 0) return false;
    }

    return true;
}

void DFS(const string& numbers, string str, unordered_set<int>& prime_num, vector<bool>& used)
{
    if (!str.empty())
    {
        if (isprimenum(str)) prime_num.insert(stoi(str));
    }

    for (int i = 0; i < numbers.length(); ++i)
    {
        if (used[i]) continue;

        used[i] = true;
        DFS(numbers, str + numbers[i], prime_num, used);
        used[i] = false;
    }
}

int solution(string numbers)
{
    unordered_set<int> prime_num;
    vector<bool> used(numbers.length(), false);

    DFS(numbers, "", prime_num, used);

    return prime_num.size();
}