소수를 구하는 부분은 쉽게 구현할 수 있었는데 모든 순열을 구하고 중복된 값을 제외한는 과정을 구하지 못해서 다른 사람의 코드를 참고 했다.
1. 숫자 n이 들어 왔을 때 소수인지 판별- 에라토스테네스의 체
bool isPrimeNumber(int n) { if (n<2) return false; for (int i=2; i<=sqrt(n); i++) if (n%i==0) return false; return true; }
처음에는 for문을 i=2 to i=n-1 까지 돌리는 코드를 작성 하였는데 에라토스테네스의 체 라는 방법을 배웠다.
<위키백과 참조>
1. 소수를 구하고자 하는 구간의 모든 수를 나열
2. 2는 소수 - 2의 배수를 모두 지운다
3. 3은 소수 - 3의 배수를 모두 지운다
4. 5는 소수 - 5의 배수를 모두 지운다
5. 7은 소수 - 7의 배수를 모두 지운다
6. 이 과정을 반복, 구간에 모둔 소수가 남는다
7. 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다
2. 주어진 numbers에 적힌 글자 하나 하나를 char v 에 담는다
vector<char> v; for (int i=0; i<numbers.size(); i++) v.push_back(numbers[i]); sort (v.begin(), v.end());
3. next_permutation 함수를 사용하여 모든 순열을 구한다
vector<int> nums; do { string temp=""; for (int i=0; i<v.size(); i++) { temp.push_back(v[i]); nums.push_back(stoi(temp)); } }while (next_permutation(v.begin(), v.end()));
e.g) 0 1 1
next_permutation 함수를 이용하면 while문을 한 번씩 돌 때마다 v에는 0 1 1, 1 0 1, 1 1 0 이 저장된다.
v에 0 1 1 이 저장되었을 때, nums에는 0, 1(01), 11(011)이 push
v에 1 0 1 이 저장되었을 때, nums에는 1, 10, 101이 push
v에 1 1 0 이 저장되었을 때, nums에는 1, 11, 110이 push
4. 정렬을 한 뒤 중복된 순열을 제거한다
sort (nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()),nums.end());
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
bool isPrimeNumber(int n) {
if (n<2)
return false;
for (int i=2; i<=sqrt(n); i++)
if (n%i==0)
return false;
return true;
}
int solution(string numbers) {
int answer = 0;
vector<char> v;
vector<int> nums;
for (int i=0; i<numbers.size(); i++)
v.push_back(numbers[i]);
sort (v.begin(), v.end());
do {
string temp="";
for (int i=0; i<v.size(); i++) {
temp.push_back(v[i]);
nums.push_back(stoi(temp));
}
}while (next_permutation(v.begin(), v.end()));
sort (nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()),nums.end());
for (int i=0; i<nums.size(); i++)
if (isPrimeNumber(nums[i])) answer++;
return answer;
}