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

1. 문제

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

2. 코드

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int solution(string numbers) {
    int answer=0;
    
    //next_permutation을 사용
    //순열 계산에서 1자리,2자리 ~ n자리만 사용하는 모든 경우의 수 구하기
    sort(numbers.begin(),numbers.end());
    vector<unsigned int> nums;
    string sub;
    do {
        for (int i = 1; i <=  numbers.size(); i++)
        {
            sub = numbers.substr(0, i);
            nums.push_back(stoi(sub));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));
    
    //중복된 숫자 제거하기
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(),nums.end()), nums.end());
    
    //에라토스테네스체 구하기
    unsigned int nn=9999999;
    vector<bool> isPrimeNum(nn+1);
    isPrimeNum[1] = true; // 1은 소수가 아니므로 true
    for(unsigned int i = 2; i <= sqrt(nn); i++){
        if(isPrimeNum[i]) continue; // 이미 true면 계산 제외
        for(unsigned int j = i + i; j <= nn; j += i) // i를 제외한 i의 배수들은 소수가 아니다.
            isPrimeNum[j] = true;
    }

    for(int i=0;i<nums.size();i++){
	    if(!isPrimeNum[nums[i]]&nums[i]>0)      //0인 경우 제외
            answer++;
    }
    
    return answer;
}

 

3. 해설

    //next_permutation을 사용
    //순열 계산에서 1자리,2자리 ~ n자리만 사용하는 모든 경우의 수 구하기
    sort(numbers.begin(),numbers.end());
    vector<unsigned int> nums;
    string sub;
    do {
        for (int i = 1; i <=  numbers.size(); i++)
        {
            sub = numbers.substr(0, i);
            nums.push_back(stoi(sub));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

먼저 경우의 수를 구하기 위해서 string을 정렬해주고, next_permutation 함수를 통해 1~n자리의 모든 경우의 수를 구합니다.

    //중복된 숫자 제거하기
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(),nums.end()), nums.end());

그 후, 중복 경우의 수가 있을 수 있으므로, 중복된 숫자를 제거해줍니다.

    //에라토스테네스체 구하기
    unsigned int nn=9999999;
    vector<bool> isPrimeNum(nn+1);
    isPrimeNum[1] = true; // 1은 소수가 아니므로 true
    for(unsigned int i = 2; i <= sqrt(nn); i++){
        if(isPrimeNum[i]) continue; // 이미 true면 계산 제외
        for(unsigned int j = i + i; j <= nn; j += i) // i를 제외한 i의 배수들은 소수가 아니다.
            isPrimeNum[j] = true;
    }

에라토스테네스체의 해 알고리즘을 이용하여 주어진 범위 내에서 소수가 아닌 값들을 true로 표시해줍니다.

    for(int i=0;i<nums.size();i++){
	    if(!isPrimeNum[nums[i]]&nums[i]>0)      //0인 경우 제외
            answer++;
    }

소수 판별 vector isPrimeNum을 가지고 경우의 수들의 리스트 nums의 값과 비교하여 만약 소수가 아닌 경우(false) answer을 한개 늘려줍니다.

경우의 수가 0인경우는 소수가 아니기 떄문에 제외합니다.