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

프로그래머스

 

📄 문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

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

 

📝 풀이

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

using namespace std;

int sel[7];
bool ch[7];
vector<bool> v;
set<string> duplicatedSet;
int answer = 0;

void DFS(string numbers, int select, int s)
{
    if(s == select)
    {
        string num;
        for(int i = 0; i < select; ++i)
            num.push_back(numbers[sel[i]]);
            
        while(num.size() > 0)
            if(num[0] == '0')
                num.erase(0, 1);
            else
                break;
        
        if(num.size() > 0 && duplicatedSet.find(num) == duplicatedSet.end())
        {
            duplicatedSet.insert(num);
            if(v[stoi(num)])
                ++answer;
        }
    }
    else
    {
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(!ch[i])
            {
                ch[i] = true;
                sel[s] = i;
                DFS(numbers, select, s + 1);
                ch[i] = false;
            }
        }
    }
}

int solution(string numbers) {

    sort(numbers.begin(), numbers.end(), greater<int>());
    int num = stoi(numbers);

    v = vector<bool>(num, true);
    v[0] = v[1] = false;
    
    for(int i = 2; i <= sqrt(num); ++i)
        for(int j = i * 2; j <= num; j += i)
            v[j] = false;
    
    for(int i = 1; i <= numbers.size(); ++i)
        DFS(numbers, i, 0);
    
    return answer;
}

• DFS를 이용하여 numbers를 뽑을 수 있는 모든 경우의 수를 뽑아서 찾습니다.
• 찾은 수열에서 앞자리 0을 제거한 후 중복되는지 확인하기위해 set을 이용합니다.
• 에라스토테네스의 체를 이용하여 numbers에서 가장 큰 값에 대한 모든 소수를 빠르게 찾은 후 v벡터에 저장합니다.
• 수열에서 v 벡터의 값을 비교하여 해당 값이 소수이면, answer의 값을 1씩 올려 정답을 리턴합니다.