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