소수 찾기

들어가는 말

숫자로 주어진 문자열로 가능한 숫자를 모두 만들어서 소수의 갯수를 구해주는 문제다. 문자열을 모두 떼서 순열을 이용해 가능한 모든 수를 구해주고 소수를 검사해주면 되겠다고 생각했다.
다만, 문제가 있었으니 next_permutation()을 써도 괜찮을까였다. 저번 sort문제에서는 못 쓰게 해서... 다른 이들의 풀이를 찾아봤더니 next_permutation을 쓰는 거 아닌가. 도대체 기준이 뭔데? 아마 시간 복잡도의 차이인 거 같은데. 흠. 그래서 나도 next_permutation을 썼다.

코드 설명

하나씩 차례로 해주면 된다.

일단 주어진 numbers string에 있는 문자들을 하나씩 나눠서 char 벡터인 c에 넣어준다.

다음 이 문자들로 순열을 만들어 주는데 next_permutation을 쓰면 된다. 여기서 주의점이 있다. 숫자 조각들로 만들 수 있는 모든 경우를 전부 넣어줘야 한다는 거다. 처음에는 이 부분을 빼서 테스트의 일부분이 틀렸다.

이렇게 숫자를 넣어주면 분명 중복된 값이 생길 거다. 이 중복된 값을 sort()와 erase(), unique()를 이용해서 제거해준다.

마지막으로 에라토스테네스의 체로 소수를 더해주면 된다. 에라토스테네스의 체는 내가 다른 글에서 설명했다. 그래도 간단히 이야기 하자면 주어진 숫자 num을 num의 약수로 전부 나눠서 만일 하나로도 나눠 떨어지면 false를 반환하도록 하는 것이다. 즉, 1과 자기 자신만이 약수 여야 하는 조건에 위배되어 소수가 아니게 되는 거다. 여기서 조심해야 하는 건 0과 1은 무조건 소수가 아니라는 점. 그렇기에 만일 주어진 숫자가 2보다 작을 경우 false를 반환하도록 했다. decimal 함수에서 true를 반환해 소수임이 판명났을 경우 answer에 ++를 해줘서 소수의 갯수를 구해주면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

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

    return true;
}


int solution(string numbers) {
    int answer = 0;
    vector<char> c;
    vector<int> ii;
    string s_per = "";

    
    /*숫자를 하나씩 떼서 벡터에 넣어준다.*/
    for(int i=0; i<numbers.size(); i++){
        c.push_back(numbers[i]);
    }
    
    /*순열을 만들어 준다.*/
    sort(c.begin(), c.end());
    do{
        s_per = "";
        for(auto it = c.begin(); it != c.end(); it++){
            ii.push_back(*it-'0');
            s_per += *it;
            ii.push_back(stoi(s_per));
        }
        ii.push_back(stoi(s_per));
    }while(next_permutation(c.begin(), c.end()));
    
    /*중복된 값을 제거*/
    sort(ii.begin(), ii.end());
    ii.erase(unique(ii.begin(), ii.end()), ii.end());
    
    /*에라토스테네스의 체로 소수만 골라준다.*/
    
    for(auto i : ii){
        if(decimal(i)){
            answer++;
        }
    }
    
    /*숫자를 만들어서 검사한다. */
    return answer;
}