[프로그래머스] 소수 찾기 (C++)

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

코딩테스트 연습 - 소수 찾기

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#define MAX 8
using namespace std;

bool check[MAX]={false,};
int sieves[10000000];
set<int> ans;

void primenumSieve(int num){
    sieves[0]=0; 
    sieves[1]=0;
    for (int i=2; i<=num; i++){
        sieves[i]=i;
    }
    for (int i=2; i<=num; i++){
        if (sieves[i]==0){
            continue;
        }
        for (int j=i+i; j<=num; j+=i){
            sieves[j]=0;
        }
    }
}

void permutation(int depth, int r, string src, string p){
    if (depth==r){
        int a=stoi(p);
        if (sieves[a]!=0){
            ans.insert(a);
        }
    }
    else{
        for (int i=0; i<src.size(); i++){
            if (!check[i]){
                check[i]=true;
                p+=src[i];
                permutation(p.size(), r, src, p);
                check[i]=false;
                p.pop_back();
            }
        }
    }
}

int solution(string numbers) {
    sort(numbers.begin(), numbers.end(), greater<>());
    int num=stoi(numbers);
    primenumSieve(num);
    for (int i=1; i<=numbers.size(); i++){
        permutation(0,i,numbers,"");
    }
    if (!ans.empty()){
        return ans.size();
    }
    return 0;
}

에라토스테네스의 체로 최대 범위까지 소수를 표시해둔다.(소수이면 0이 아닌걸로)

순열로 가능한 수를 모두 찾는다.

가능한 수 중, 소수인지 판별해서 소수인 것을 set 에 넣는다.(set에 넣는 것은 중복을 피하기 위함.)

 

순열+에라테스테네스의 체를 합친 문제.

 

난 여기서 n개의 문자가 있으면, n개 중 1개를 뽑는.. n개 중 2개를 뽑는.. n개 중 n개를 뽑도록 반복문을 돌려주었다.

그런데 이럴 필요 없이, n개 중 n개를 뽑는 순열을 만드는 과정 도중 문자열을 set 자료 구조에 저장해서 소수인지 따져주면 된다.

    if(depth == limit) return;
    
    for(int i = 0 ; i < limit ; i++){
        if(!check[i]){
            check[i] = true;
            str.push_back(numbers[i]);
            s.insert(stoi(str));
            find_all_numbers(depth+1, limit, numbers);
            str.pop_back();
            check[i] = false;
        }
    }