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

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

프로그래머스

 

숫자로 이루어진 문자열 numbers 가 주어졌을 때, 각각의 숫자로 만들 수 있는 수 중에서 소수의 개수를 찾아서 반환하면 된다. 문자열 numbers 에 등장하는 숫자들로 만들 수 있는 모든 숫자를 만들어서 소수의 개수를 판단하면 된다. 이를 위해서 next_permuation 을 이용하여, 각각의 문자열의 숫자들로 만들 수 있는 모든 순열을 만든 다음 각 자릿수를 substr 을 이용해서 잘라준 뒤 소수 판별 함수에 넣고, 소수가 맞으면 unordered_set 에 넣어준다. 그러면 unordered_set 에서는 소수 원소만 중복없이 들어가게 되므로, 최종적인 답안 answer 은 unordered_set 의 크기가 된다.

 

 

[C++]

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


using namespace std;

bool isprime(int n){
    if(n == 0 || n == 1) 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;
    unordered_set<int> st;
    sort(numbers.begin(), numbers.end());
    do{
        for(int i = 1 ; i <= numbers.size(); i ++)
        {
            int num = stoi(numbers.substr(0, i));;
            if(isprime(num) == true)
            {
                st.insert(num);
            }
        }
    }while(next_permutation(numbers.begin(), numbers.end()));
    
    answer = st.size();
    return answer;
}