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

1.문제 링크

소수 찾기

2. 풀이 전 계획과 생각

• 조합이용

3. 풀이

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

bool isPrime(int n) {
    if (n < 2) return false;
    // 에라토스테네스의 체
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<char> nums;
    vector<int> unique_nums;

    for(int i=0;i<numbers.size();i++) nums.push_back(numbers[i]);
    sort(nums.begin(), nums.end());
    do {
        string temp = "";
        for (int i = 0; i < nums.size(); i++) {
            temp.push_back(nums[i]);
            unique_nums.push_back(stoi(temp));
        }
    } while (next_permutation(nums.begin(), nums.end()));

     //중복 제거
    sort(unique_nums.begin(), unique_nums.end());
    unique_nums.erase(unique(unique_nums.begin(), unique_nums.end()), unique_nums.end());
    for (int i = 0; i < unique_nums.size(); i++) if (isPrime(unique_nums[i])) answer++;

    return answer;
}

4. 풀이하면서 고민했던 점

-

5. 문제를 풀고 알게된 개념 및 소감

• next_permutation 사용시 오름차순 정렬을 해야한다. next_permutation은 더 큰 순열을로 재배열을 할 수 있으면 반복하여 구해내는 구조이므로 앞에 이미 큰 원소들이 배치되어 있으면 반복하지 않게 됩니다. 만약 데이터가 내림차순으로 정렬이되어 있다면 next_permutation 대신 prev_permutation을 사용하면 된다.

• unique 함수 사용시 sort 되어 있어야 한다.

• unique 함수와 erase함수를 사용해 벡터내 중복 원소 제거 방법을 알게됨.