[C++] 프로그래머스 소수 찾기 풀이

주어진 숫자들로 조합할 수 있는 숫자들 중 소수가 몇 개인지 찾는 문제

 

---

문제의 조건

 

1. string으로 변환된 숫자 numbers가 주어짐 

 

2. numbers의 각 숫자들을 조합해서 만들 수 있는 숫자들 중 소수를 찾아서 카운트하기 

 

3. 여기서 조합이 가능한 모든 경우를 탐색한 후 중복되는 숫자는 거르고 소수를 찾아야 함

순열을 찾아주는 함수가 있는줄 모르고 저것을 직접 구현하려다 피 봤는데...

next_permutation이라는.. 친절하게 모든 순열을 구해주는 함수가 있으니까 저걸 쓰자. 

 

---

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool isPrimeNum(int num)
{
    if (2 > num) return false;

    //소수를 판별할 땐 2부터 제곱근까지만 계산해보면 된다. 
    int a = static_cast<int>(sqrt(num));
    for (int i = 2; a >= i; i++)
    {
        if (0 == num % i) return false;
    }

    return true;
}

int solution(string numbers) {
    int answer = 0;
    //numbers 분해해서 한 조각씩 따로 저장 
    vector<char> pieces;
    for (int i = 0; numbers.length() > i; i++)
        pieces.emplace_back(numbers[i]);

    //next_permutation 함수를 쓰려면 오름차순 정렬이 되어 있어야 함 
    sort(pieces.begin(), pieces.end());

    vector<int> newNumbers;

    //next_permutation 함수를 거치고 나면 벡터에 정렬된 순서가 다음 순열을 구하기 위한 순서로 바껴있음 
    //그래서 조합이 가능한 경우를 쉽게 구할 수 있다. 
    do {
        string str = "";
        for (int i = 0; pieces.size() > i; i++)
        {
            str += pieces[i];
            newNumbers.emplace_back(stoi(str));
        }
    } while (next_permutation(pieces.begin(), pieces.end()));

    //중복되는 숫자를 제거하기 위해 오름차순 정렬 후 unique 함수 실행 
    sort(newNumbers.begin(), newNumbers.end());
    newNumbers.resize(unique(newNumbers.begin(), newNumbers.end()) - newNumbers.begin());

    for (auto num: newNumbers)
    {
        if (isPrimeNum(num))
            answer++;
    }

    return answer;
}