Level 2
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
numbers | return |
---|---|
"17" | 3 |
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
bool sosu(int n) { // 소수 판별 함수
if(n < 2)
return false;
int s = (int) sqrt(n); // 루트 n
for(int i=2; i <= s; i++) {
if(n % i == 0)
return false;
}
return true;
}
int solution(string numbers) {
int answer = 0;
vector<int> numbersInt;
vector<int> finalInt;
for(int i=0; i<numbers[i]; i++)
numbersInt.push_back(numbers[i] - '0');
sort(numbersInt.begin(), numbersInt.end());
do {
for(int i=0; i<=numbersInt.size(); i++) {
int temp = 0;
for(int j=0; j<i; j++) {
temp = (temp*10) + numbersInt[j];
finalInt.push_back(temp);
}
}
} while(next_permutation(numbersInt.begin(), numbersInt.end()));
sort(finalInt.begin(), finalInt.end());
finalInt.erase(unique(finalInt.begin(), finalInt.end()), finalInt.end());
for(int i=0; i<finalInt.size(); i++) {
if(sosu(finalInt[i]))
answer++;
}
return answer;
}