프로그래머스 소수찾기 c++ // 순열 3P1+3P2+3P3 하는방법, 소수판별함수, dfs

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

프로그래머스

1. 순열 3P1+3P2+3P3 하는방법

do{
    string s="";
    for(int i=0;i<n;++i){
        //cout<<v[i]<<" ";
        s+=numbers[v[i]];
        se.insert(stoi(s)); //for문안에서 push => 3P1,3P2,3P3차례대로 들어감!
    }
    //cout<<"\n";
}while(next_permutation(v.begin(),v.end()));

for문안에서 set에 넣으면된다.

ex) 0 1 2 : 0, 01, 012

0 2 1 : 0, 02, 021 ... 모든경우의수(nP1+nP2+...nPn)가 들어가게된다

 

2. 소수판별함수

// 소수 판별 함수
bool isPrime(int n) {
    if (n < 2) return false;

    // 에라토스테네스의 체
    //i : 2~루트n
    //약수i가 존재? -> 소수아님
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;

    return true;
}

3. 순열풀이

#include <bits/stdc++.h>

using namespace std;

int is_prime[10000000],n,ret;
set<int> se;

// 소수 판별 함수
bool isPrime(int n) {
    if (n < 2) return false;

    // 에라토스테네스의 체
    //i : 2~루트n
    //약수i가 존재? -> 소수아님
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;

    return true;
}
int solution(string numbers) {
    n=numbers.size();

    vector<int> v;
    for(int i=0;i<n;++i) v.push_back(i);
    
    do{
        string s="";
        for(int i=0;i<n;++i){
            //cout<<v[i]<<" ";
            s+=numbers[v[i]];
            se.insert(stoi(s)); //for문안에서 push => 3P1,3P2,3P3차례대로 들어감!
        }
        //cout<<"\n";
    }while(next_permutation(v.begin(),v.end()));
    
    
    //cout<<"=====================\n";
    for(auto i : se){
        //cout<<i<<"\n";
        if(isPrime(i)) ret++;
    }
    return ret;
}

 

4.dfs 풀이

#include <bits/stdc++.h>

using namespace std;

int vis[10],n,ret;
set<int> se;

// 소수 판별 함수
bool isPrime(int n) {
    if (n < 2) return false;

    // 에라토스테네스의 체
    //i : 2~루트n
    //약수i가 존재? -> 소수아님
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;

    
    return true;
}
void dfs(string& numbers, string result){
    if(result.size()){
        se.insert(stoi(result));
    }
    
    for(int i=0;i<n;++i){
        if(vis[i]) continue;
        vis[i]=1;
        dfs(numbers,result+numbers[i]);
        vis[i]=0;
    }
}
int solution(string numbers) {
    n=numbers.size();

    dfs(numbers,"");
    
    for(auto i : se){
        if(isPrime(i)) ret++;
    }
    return ret;
}