[문제]
programmers.co.kr/learn/courses/30/lessons/42839
코딩테스트 연습 - 소수 찾기
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이
programmers.co.kr
[풀이]
에라토스테네스의 체 , 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();
}
