99클럽 코테 스터디 15일차 TIL, 프로그래머스 / 소수찾기

 

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

using namespace std;

vector<bool> visited;
string originNums;
set<int> candidates;

bool isPrime(int n)
{
    if (n == 0 || n == 1)
        return false;
    // 2 ~ n-1 
    for (int x = 2; x < n; ++x)
        if (n % x == 0)
            return false;
    return true;
}

void getAllPapers(string& curN, int prevIdx)
{
    if (curN.size() != 0)
    {
        candidates.insert(stoi(curN));
        
        if (curN.size() == visited.size())
            return;
    }
    
    for (int i = 0; i < visited.size(); ++i)
    {
        if (visited[i])
            continue;
        
        visited[i] = true;
        curN.push_back(originNums[i]);
        getAllPapers(curN, i);
        curN.pop_back();
        visited[i] = false;
    }
}

int solution(string numbers) 
{
    string curNum;
    int answer      = 0;
    originNums      = numbers;
    visited.resize(originNums.size());
    
    for (int i = 0; i < visited.size(); ++i) 
        visited[i] = false;
    
    getAllPapers(curNum, -1);
    
    for (const int& cand : candidates)
    {
        if (isPrime(cand) == false)
            continue;
        // cout << cand << endl;
        answer += 1;
    }
    
    return answer;
}

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

프로그래머스