Programming/Algorithm

[Level2 프로그래머스] 소수 찾기, c++

SNOWOO 2021. 10. 1. 16:01
728x90

문제 설명

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

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

 

제한사항

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

입출력

numbers return
"17" 3
"011" 2

문제 풀이

1. 문자열이 주어졌을때 문자열을 조합해서 만들수 있는 모든 문자열을 만든다.

2. 만들어진 문자열이 소수인지 아닌지 확인한다.

 


소스 코드

 

#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
bool selected[7];
vector<char> v;
vector<char> v2;
vector<int> list;
int ans;
bool isPrime(int tmp)
{
    if(tmp == 1 || tmp == 0)
        return false;
    int num = (int)sqrt(tmp);
    for(int i=2;i<=num;i++)
    {
        if(tmp%i ==0)
            return false;
    }
    return true;
}
void dfs(int cnt, int depth)
{
    if(cnt == depth)
    {
        string tmp ="";
        for(auto a : v2)
            tmp += a;
        if(find(list.begin(), list.end(), stoi(tmp)) == list.end())
        {
            list.push_back(stoi(tmp));
            if(isPrime(stoi(tmp)))
                ans++;
        }
        return;
    }
    for(int i=0;i<v.size();i++)
    {
        if(selected[i])continue;
        selected[i] = true;
        v2.push_back(v[i]);
        dfs(cnt, depth+1);
        v2.pop_back();
        selected[i] =false;
    }
}
int solution(string s)
{
    ans = 0;
    for(int i=0;i<s.size();i++)
    {
        v.push_back(s[i]);
    }
    for(int i=1;i<s.size()+1;i++)
    {
        dfs(i,0);
    }
    return ans;
}
LIST