반응형
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42839
문제
풀이과정
우선 이 문제는 모든 수의 조합에 대해서 확인을 해야합니다.
문제의 예시를 보게 되면 17이면 7 17 71이라는 소수를 만듭니다. 즉 모든 숫자의 조합을 확인해봐야 하기때문에
algoirthm헤더에서 next_permutation을 사용합니다.
또한 모든 조합을 얻었을때 같은 숫자에 대해서는 중복을 제거합니다.
진행과정
1. 모든 조합에 대해서 진행 (do~while next_permutation)
2. 모든 조합에 대한 추가한 벡터에 중복 제거 (erase+unique)
3. 소수제거 -> 짝수에 대해서 미리 제거하고 숫자의 제곱근까지의 소수판별을 합니다.
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int solution(string numbers) {
int answer = 0;
vector<int> v;
vector<int> permutation; //모든 조합들에 대한 백터
for(int i = 0 ; i< numbers.length();i++){
v.push_back((numbers[i] - '0'));
}
sort(v.begin(),v.end());
do{
int num = 0;
for(int i = 0; i < v.size();i++){
num *= 10;
num += v[i];
permutation.push_back(num);
}
}while(next_permutation(v.begin(),v.end())); //모든 조합에 대해서 진행
sort(permutation.begin(),permutation.end()); //모든 조합들에 대해 정렬
permutation.erase(unique(permutation.begin(),permutation.end()),permutation.end()); //중복 제거
for(int i = 0; i < permutation.size();i++){
int PrimeFlag = 1; //소수플래그
if(permutation[i] < 2)
continue; // 0혹은 1은 소수아님
else if(permutation[i] == 2){
answer++;
continue;
}
for(int j = 2;j<=sqrt(permutation[i]);j++){
if(permutation[i] % j == 0 || permutation[i] % 2 == 0){
PrimeFlag = 0;
break;
}
}
if(PrimeFlag == 1){ //소수일때 ++
answer++;
}
}
return answer;
}
반응형
'알고리즘 > c++ 프로그래머스' 카테고리의 다른 글
[프로그래머스 공원 산책] c++ (풀이,코드) (0) | 2023.06.19 |
---|---|
[프로그래머스 x만큼 간격이 있는 n개의 숫자] c++ (풀이,코드) (0) | 2023.06.19 |
[프로그래머스 가장 큰수] c++ (풀이,코드) (0) | 2023.06.10 |
[프로그래머스 다리를 지나는 트럭] c++ (풀이,코드) (0) | 2023.06.08 |
[프로그래머스 롤케이크 자르기] c++ (풀이, 코드) (0) | 2023.06.07 |
댓글