[프로그래머스]완전탐색 : 소수 찾기 (level 2)(c++)

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

프로그래머스

 

방법 1: DFS

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int MAX = 10000000;
int isno_prime[MAX + 1] = {1, 1, };
int bf;
int cnt;
 
void seive_of_eratosthenes(int max)
{
    for (int i = 2; i * i <= max; i++)
    {
        if (isno_prime[i] == false)
        {
            for (int j = 2; i * j <= max; j++)
            {
                isno_prime[i * j] = true;
            }
        }
    }
}
 
// nPr 가지의 수 모두 구하기
void perm(const string &numbers, string output, bool visited[], int depth, int r)
{
    if (depth == r)
    {
        int res = stoi(output);
        // numbers가 오름차순 정렬되었으므로, 이전 숫자보다 큰 수만 카운팅해도 OK
        // 동일 숫자는 카운팅 하지 않으므로 결과적으로 nCr
        if (bf < res && !isno_prime[res])
        {
            bf = res;
            cnt++;
        }
        return;
    }
 
    for (int i = 0; i < numbers.size(); i++)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            perm(numbers, output + numbers[i], visited, depth + 1, r);
            visited[i] = false;
        }
    }
}
 
int solution(string numbers) {
 
    // 내림차순 정렬
    sort(numbers.begin(), numbers.end(), [](int a, int b) {
        return a > b;
        });
 
    // 에라토스테네스의 체로 소수 구분 - 최대값까지만 
    seive_of_eratosthenes(stoi(numbers));
    
    // 오름차순 정렬
    sort(numbers.begin(), numbers.end());
 
    // nPr(1 <= r <= n) 가지의 경우를 모두 계산하며
    // 나올수 있는 소수 구하기
    const int MAX_SIZE = 7;
    bool visited[MAX_SIZE] = {0,};
    for (int i = 1; i <= numbers.size(); i++)
    {
        perm(numbers, "", visited, 0, i);
    }
 
    return cnt;
}

 

 

방법 2: set와 next_permutation() 활용

#include <string>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
const int MAX = 10000000;
int isno_prime[MAX + 1] = { 1, 1, };
 
void seive_of_eratosthenes(int max)
{
    for (int i = 2; i * i <= max; i++)
    {
        if (isno_prime[i] == false)
        {
            for (int j = 2; i * j <= max; j++)
            {
                isno_prime[i * j] = true;
            }
        }
    }
}
 
int solution(string numbers) {
 
    // 내림차순 정렬
    sort(numbers.begin(), numbers.end(), [](int a, int b) {
        return a > b;
        });
 
    // 에라토스테네스의 체로 소수 구분 - 최대값까지만 
    seive_of_eratosthenes(stoi(numbers));
 
    // 오름차순 정렬
    sort(numbers.begin(), numbers.end());
 
    // 중복되지 않는 조합의 소수 찾기
    set<int> prime_set;
    do
    {
        for (int i = 1; i <= numbers.size(); i++)
        {
            int res = stoi(numbers.substr(0, i));
 
            if (!isno_prime[res])
            {
                prime_set.insert(res);
            }
        }
 
    } while (next_permutation(numbers.begin(), numbers.end()));
 
    return prime_set.size();
}

 

 

방법 2는 다른 분 풀이를 좀 참고했다.

속도는 크게 차이나지 않는다.

 

TIP

next_permutation을 쓰려면 먼저 오름차순 정렬을 해야한다. 

 

 

순열 알고리즘을 잘 설명한 블로그 : 

https://minusi.tistory.com/entry/%EC%88%9C%EC%97%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Permutation-Algorithm