[Lv.2] 소수 찾기

문제 설명

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

구현해야할 조건

모든 값에 대해서 조합을 만들어서 구현해야하는데, next_permutation을 사용해서 중복된것을 처리하면서 문제를 해결했다. 왜냐면 numbers는 아무리 길어도 7이기 때문에 조합이 가능하다! 그후 소수 판별함수를 만들었는데, 맨날 소수 판별하는거 어려워하는데 한번 이해를 할 필요가 있다고 생각한다!

code

 

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

using namespace std;

bool Prime_chk(int n)
{
    if(n < 2)
        return false;
    
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<int> number;
    
    for(int i = 0; i < numbers.size(); i++)
        number.push_back(numbers[i] - '0');
    
    sort(number.begin(), number.end());
    vector<int> ans;
    
    do{
        
        for(int i = 1; i <= number.size(); i++)
        {
            int temp = 0;
            
            for(int j = 0; j < i; j++)
            {
                temp = (temp * 10) + number[j];
                ans.push_back(temp);
                // cout << temp << "\n";
            }
        }
        
    }while(next_permutation(number.begin(), number.end()));
    
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    
    for(int i = 0; i < ans.size(); i++)
    {
        if(Prime_chk(ans[i]))
            answer += 1;
    }
    
    return answer;
}