소수 찾기(Level2)

• 문제 링크: 코딩테스트 연습 > 완전탐색 > 소수 찾기

• 문제 이해

  1. 주어지는 벡터 numbers의 각 수를 조합하여 만들 수 있는 소수의 개수를 구합니다.
  2. 011은 11로 취급합니다.

• 알고리즘 구현

  1. 먼저, 숫자가 소수인지 체크하는 isPrime 함수를 만들었습니다.
     (nbr을 판단할 때, 2 이상, nbr보다 작은 수로 나누어 떨어지지 않으면 소수입니다.)
  2. 주어진 numbers의 숫자를 조합하여 만들 수 있는 숫자들을 구합니다.
  3. 이를 위해, genNum이라는 함수를 만들었고, 재귀적으로 사용하여 numArr에
     요소를 추가합니다.
  4. numbers의 숫자를 순서에 관계없이 조합해야하기 때문에, visited를 사용하여,
     모든 경우의 조합을 만들어봅니다.
  5. 숫자 (nbr_tmp)가 만들어졌다면, 이 값이 numArr에 있는지 확인하고, 없다면
     numArr의 요소에 넣습니다. (nbr_tmp는 이전 수에 자릿수를 추가한 값입니다.)

• 알고리즘

#include <string>
#include <vector>

using namespace std;

bool isPrime(int nbr) {
    if (nbr == 1 || nbr == 0) return (false);
    int n = 2;
    for (int n = 2; n < nbr; ++n)
        if (nbr % n == 0) return (false);
    return (true);
}

string numbers;
int n;
void genNum(int nbr, int visited, vector<int> &numArr) {
    if (visited == ((1 << n) - 1)) return ;
    
    int nbr_tmp;
    for (int next = 0; next < n; ++next) {
        nbr_tmp = nbr;
        if (visited & (1 << next)) continue ;
        nbr_tmp = nbr * 10 + (numbers[next] - '0');
        bool isUniq = true;
        for (int i = 0; i < numArr.size(); ++i) {
            if (numArr[i] == nbr_tmp)
                isUniq = false;
        }
        if (isUniq) numArr.push_back(nbr_tmp);
        genNum(nbr_tmp, visited | (1 << next), numArr);
    }
}

int solution(string _numbers) {
    numbers = _numbers;
    n = numbers.size();
    vector<int> numArr;
    genNum(0, 0, numArr);
    int answer = 0;
    for (int i = 0; i < numArr.size(); ++i)
        if (isPrime(numArr[i])) ++answer;
    return (answer);
}