프로그래머스(C++) - 소수 찾기

●문제

 

●입출력

 

사용 알고리즘 : 완전탐색

사용 수학공식 : 에라토스테네스의 체

 

문제해석 : 현재 string타입 numbers의 숫자로 만들수있는 모든 경우의 수

ex ) 17이면 1, 7, 17, 71 중에 소수의 갯수 반환

 

푼방법 : 모든 경우의 수를 가정

단 set을 사용하여 중복인 경우를 방지 (만약 1117 인경우 1, 1, 11, 11 이렇게 중복이나온다)

모든 경우의 수에서 중복을 방지하여 set에 넣는다

재귀함수를 사용하여 풀이

 

에라토스테네스의 체 공식을 사용하여 소수를 구하는함수를 만든다

숫자 n까지의 소수를 판별하는 공식은 2부터 n의 루트 까지 계산을 하면된다 (sqrt 사용)

#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <iostream>
using namespace std;

set<int> numberSet;
bool isPrime(int number)
{
    //0과 1은 소수가 아니다
    if (number == 0 || number == 1) return false;
    //에라토스테네스의 체 사용 [ 소수는 2부터 루트n까지 확인]
    int lim = sqrt(number);
    for (int i = 2; i <= lim; i++)
    {
        //배수확인 배수면 소수 x
        if (number % i == 0) return false;
    }
    return true;
}

//comb = 현재까지 만들어진 조합 [1] [7] [17] [71] 
//others = 현재까지 사용되지않은 string
void Reculsive(string comb, string others)
{
    //현 조합을 numberSet에 추가
    if (comb != "")
    {
        numberSet.insert(stoi(comb));
    }
    //현 조합에다가 others[i]를 더해서 새로운 조합을 만들어본다
    for (int i = 0; i < others.size(); i++)
    {
        Reculsive(comb + others[i], others.substr(0, i) + others.substr(i + 1));
    }
}

int solution(string numbers)
{
    //set으로 numbers중복을 걸러내되 모든 경우의 수를 set에 담아라 사용은 재귀함수로
    //즉 모든 숫자의 조합을 짜라
    Reculsive("", numbers);
    int answer = 0;
    //에라토스테네스의 체 공식을 사용하여 sqrt함수로 2부터 루트값까지 확인해서 소수 판별
    for (int number : numberSet)
    {
        if (isPrime(number))
        {
            answer++;
        }
    }
    //소수값 ++ 출력
    return answer;
}
int main(void)
{
    cout << solution("17");
}

 

레벨 : 2

점수 : 1