소수 찾기

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

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

제한사항

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

코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

set<int> allnum;

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

void find(string now, string others) {
    if(now != "") allnum.insert(stoi(now));
    for(int i = 0; i < others.size(); i++) 
        find(now + others[i], others.substr(0, i) + others.substr(i + 1));
}

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end());
    find("", numbers);
    for(int i : allnum) {
        if(isCrime(i)) ++answer;
    }
    return answer;
}

기타

모든 조합을 어떻게 찾는가.. 고민을 많이 했지만.. 떠올리지 못하고 결국 참고.

• 숫자가 중복되면 안되므로 set 을 이용
• dfs를 이용해서 조합할 수 있는 모든 숫자 찾기

현재 문자열(숫자 조합)에 나머지 문자열(사용하지 않는 숫자)을 붙여서 새로운 수를 만들어나간다.

for(int i = 0; i < others.size(); i++)
	find(now + others[i], others.substr(0, i) + others.substr(i + 1));

이렇게 하면 모든 숫자를 만들 수 있는데...
순열 함수( next_permutation )을 사용해서 모든 조합을 구하는 방식도 있다고 한다(난 이 함수 자체를 처음 봤다)


순열 함수 이용

vector<char> v;
vector<int> nums;

for(char c : numbers) v.emplace_back(c);
sort(c.begin(), c.end());	// next_permutation은 정렬된 상태에서만 사용 가능

do {
	string s = "";
    for(int i = 0; i < v.size(); i++) {
    	s += v[i];
        nums.emplace_back(stoi(s));
    }
} while (next_permutation(v.begin(), b.end()));

// nums는 벡터이므로 중복 제거
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());

next_permutation 을 이용하면 v의 원소들이 순열 순서대로(?) 정렬된다.
예를 들어 v의 원소가 1, 2, 3 이라면 반복문을 한 번 돌면 1, 3, 2 , 그 다음은 2, 1, 3 이런 식으로.

이렇게 정렬된 원소들을 하나씩 s에 넣고( 1, 12, 123, ... ) 그 수를 nums에 넣어주면 모든 수의 조합을 얻을 수 있다.