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

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

프로그래머스

 

문제 :

 

예시 : 

 

 

해결 : 

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

using namespace std;

int answer = 0;
int visited[10];
bool isPrime[10000000];
int isCounted[10000000];
string nums = "";

// 에라토스테네스의 체
void eratostenes()
{
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i < 10000000; i++)
    {
        if(!isPrime[i]) continue;
        for(int j = 2 * i; j < 10000000; j += i)
        {
            isPrime[j] = false;
        }
    }
    
}

// 숫자 배열 가짓수 구하기
void permu(int num)
{
    if(!isCounted[num]) 
    {
        isCounted[num] = 1;
        if(isPrime[num]) answer++;
    }
        
    for(int i = 0; i < nums.size(); i++)
    {
        if(visited[i]) continue;
        int n = (int)(nums[i] - '0');
        visited[i] = 1;
        permu(num * 10 + n);
        visited[i] = 0;
    }
}

int solution(string numbers) {
    nums = numbers;
    fill(isPrime, isPrime + 10000000, true);
    eratostenes();
    permu(0);
    return answer;
}

주어진 문자열의 숫자들을 조합하여 몇 개의 소수를 만들 수 있는가를 묻는 문제이다. 

최대 7자리 수인 0~9로 이루어진 문자열이 주어지며, 여기 포함된 숫자들을 조합하여 만든 숫자들 중 소수가 몇 개인지를 구하여 리턴하면된다.

 

예를 들어 "123"이라는 문자열이 주어진다면, [1, 2, 3, 12, 13, 21, 23, 31, 32, 123]의 숫자들을 만들 수 있다. 이 중 소수는 [2, 3, 13, 23, 31]이므로 소수의 개수인 5를 출력하면 된다. 

 

이 문제를 해결하기 위해서는 소수인지 아닌지를 구하는 방법인 '에라토스테네스의 체'와 주어진 숫자들을 배열하는 가짓수를 구하는 '순열 알고리즘'을 구현하여야 한다. 

 

시간복잡도는 숫자들의 가짓수를 구하는 시간인 O(문자열의 길이!)과 에라토스테네스의 체를 구하는 시간인 O(Nlog(log N))을 더한 값이 된다. 

 

 

참고 : 

에라토스테네스 관련 블로그 :

https://maramarathon.tistory.com/39

소수 판별 알고리즘과 에라토스테네스의 체

https://blog.encrypted.gg/983

[실전 알고리즘] 0x12강 - 수학