[프로그래머스] 소수 찾기

[문제]

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

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

 

[풀이]

 

에라토스테네스의 체 , next_permutation, set를 모두 공부할 수 있는 문제

 

에라토스테네스의 체는 어떤 수가 소수인지 아닌지 판별할 때 사용된다. 

 

1. 소수를 판별할 만큼 배열을 할당하고 배열을 자기 자신으로 초기화한다.

2. 2부터 자기 자신에 해당하는 것을 제외하고 배수들은 모두 0으로 바꿔서 소수에서 제외시킨다. 

 

#define MAX 10000

int arr[MAX]={0,};

void Eratos(int num)
{
    for(int i=1;i<=num;i++)
        arr[i] = i;
    
    for(int i=2 ; i<=num;i++){
        for(int j=2*i;j<=num;j+=i ){
            arr[i]=0;
        }
    }
    
    for(int i=2;i<=num;i++){
        if(arr[i]!=0)
            printf("%d",i);
    }
}

 

 

 next_permutation은 헤더에 algorithm을 추가하면 사용할 수 있는 STL이다.

벡터나 배열로 사용이 가능하며 가능한 모든 조합을 구할 수 있다.

단, 사용하기 전에 벡터나 배열이 오름차순으로 정렬되어 있어야 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
    vector <int> v;
    
    for(int i=5;i>=2;i--)   v.push_back(i);
    sort(v.begin(),v.end());
    do{
        for(int i=0;i<v.size();i++) cout << v[i];
        cout << endl;
    }while(next_permutation(v.begin(), v.end()));
    
    return  0;
}

아래 사진과 같이 벡터의 모든 조합을 구할 수 있다.

 

 

set은 중복이 허용되지 않고 자동으로 오름차순 정렬이 된다.

 

 

 

======================================================

 

문제 풀이

 

1. input으로 주어진 numbers를 내림차순으로 정렬하여 number로 만들 수 있는 숫자 중에서 가장 큰 수를 구한다.

2. 에라토스테네스의 체를 사용해 가장 큰 수 까지 소수인지 아닌지를 판별

3. 다시 numbers를 오름차순으로 정렬하여 next_permutation을 사용해 가능한 모든 조합을 구한다.

이 때 해당 숫자가 소수이고 set에 존재하지 않는다면  set에 insert

 

[코드]

 

#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector <int> v;
int IsPrime[10000000]={0,};
int cnt=0;

bool comp(int a, int b)
{
    if(a > b )  return true;
    return false;
}

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

int solution(string numbers) {
    int answer = 0;
    set <int> s;
    
    sort(numbers.begin(), numbers.end(),comp);
    int num = stoi(numbers);

    Eratos(num);
    
    sort(numbers.begin(), numbers.end());
    
    do{
        for(int i=1;i<=numbers.size();i++)
        {
            string tmp1 = numbers.substr(0,i);
            num = stoi(tmp1);
            
            if(IsPrime[num]!= 0 )    s.insert(num);
        }
    }while(next_permutation(numbers.begin(),numbers.end()));

    return s.size();
}