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

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

• https://school.programmers.co.kr/learn/courses/30/lessons/42839#

• 주의해야할 예제

intput: "17"
answer: 3 

• [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있다
  -> 1,7로 만들 수 있는 모든 문자열을 검사하기 위해 next_permutation 함수 사용

• next_permutation 함수 사용 전에 반드시 sort 해주어야 한다

sort(str.begin(), str.end());
do{
	...        
}while(next_permutation(str.begin(), str.end()));

풀이

#include <string>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iostream>

using namespace std;

string globalnumbers;
set<int> primeNums;

bool isPrime(int num){
    if(num < 2) return false;
    for(int i = 2; i<= sqrt(num); ++i){
        if((num%i) == 0) return false;
    }
    return true;
}

void makeNums(int startidx, string num){    
    if(num != ""){
        sort(num.begin(), num.end());
        do{
            int numInt = stoi(num);
            if(primeNums.find(numInt) != primeNums.end()) continue;
            
            if(isPrime(numInt)){
                cout << numInt <<"\n";
                primeNums.insert(numInt);
            }
        }while(next_permutation(num.begin(), num.end()));
    }
    if(startidx == globalnumbers.length()) return;
    
    //현재 숫자 선택하지 않는 경우
    makeNums(startidx + 1, num);
    //현재 숫자 선택하는 경우
    makeNums(startidx + 1, num + globalnumbers[startidx]);
}

int solution(string numbers) {
    globalnumbers.assign(numbers);
    
    makeNums(0,"");
    
    int answer = primeNums.size();
    return answer;
}