[Programmers] Level2 : 소수 찾기

Question

---

Solution

• numbers에 있는 숫자로 만들 수 있는 모든 숫자를 찾아 만들어야 한다.
  이때 dfs + 백트래킹을 이용하여 만들 수 있다.
• 소수인지 판별 할때 중복되는 숫자를 제거하기 위해 만들어지는 숫자를 set에 저장한다.

---

Cord

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

using namespace std;

set<int> uniqeNums;
vector<bool> visited(7);

// dfs + 백 트래킹
// 1 -> 12 -> 123 -> 1234 -> 123 -> 12 -> 124 -> 1243 -> 124 -> 12 -> 1 -> 13 ...
void dfs(string num, string numbers)
{
    if (!num.empty()) { uniqeNums.insert(stoi(num)); }

    for (int i = 0; i < numbers.size(); ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            dfs(num + numbers[i], numbers);
            visited[i] = false;
        }
    }
}

// 소수 판별
bool isPrimeNum(int num)
{
    if (num < 2) { return false; }

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

    return true;
}

int solution(string numbers)
{
    int answer = 0;
    
    dfs("", numbers);

    for (auto iter = uniqeNums.begin(); iter != uniqeNums.end(); ++iter)
    {
        answer += isPrimeNum(*iter);
    }

    return answer;
}

---

Result