[Programmers] (완전탐색) Lv 2. 소수 찾기

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

프로그래머스

 

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

using namespace std;

const bool IsPrime(int n)
{
    for (size_t i = 2; i <= sqrt(n); ++i)
        if (n % i == 0) return false;
    return true && n > 1;
}

void expression(const string& numbers, unordered_set<int>& set, vector<int>* idxList, string num)
{
    set.insert(stoi(num));

    for (int i = 0; i < numbers.length(); ++i)
    {
        if (find(idxList->begin(), idxList->end(), i) != idxList->end()) continue;

        idxList->push_back(i); num += numbers[i];
        expression(numbers, set, idxList, num);
        idxList->pop_back(); num.pop_back();
    }
}

int solution(string numbers) {
    //24.10.21
    int answer = 0;
    unordered_set<int> set;
    
    expression(numbers, set, new vector<int>(), "0");

    for (const auto& n : set)
        answer += IsPrime(n) ? 1 : 0;

    return answer;
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/commit/b8aff5a28a52d56036c2a665dc4e9381e459a7dc

[level 2] Title: 소수 찾기, Time: 2.61 ms, Memory: 4.13 MB -BaekjoonHub · developeSHG/Algorithm-Baekjoon_Programmers@b8aff5