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

소수 찾기 / Lv.2

---

문제  설명 )

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

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

 

 

 

제한 사항 )

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

 

 

 

입출력 예 )

 

 

입출력 예 설명 )

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

 

 

 

풀이)

 

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
int n;
map<int, int> m;
string* num;
vector<int> visited;
int ans = 0;
 
 
// 소수 판별
bool check(int a)
{
    if(a == 1 || a == 0) return false;
    
    for(int i = 2; i * i <= a; i++)
    {
        if(a % i == 0) return false;
    }
    return true;
}
 
void recur(int cur, string temp)
{
    if(cur == n + 1) return;
    
    int a;
    if(temp != "")
    {
        a = stoi(temp);
    }
    
    if(cur > 0 && m.find(a) == m.end() && check(a))
    {
        ans++;
        m.insert(make_pair(a, 1));
    }
    
    for(int i = 0; i < n; i++)
    {
        if(visited[i]) continue;
        visited[i] = 1;
        recur(cur + 1, temp + (*num)[i]);
        visited[i] = 0;
    }
}
 
int solution(string numbers) {
    
    n = numbers.length();
    visited.resize(n, 0);
    num = &numbers;
    
    recur(0, "");
    
    return ans;
}

---

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42839 

프로그래머스