프로그래머스 소수 찾기 - C++

문제

---

프로그래머스

 

 

풀이

---

대략적인 풀이는 오늘 작성하고 자세한 풀이는 내일 작성하겠다... (시간 이슈)

next_permutations라는 함수가 있는데, 배열에 있는 다음 순열을 만들어주는 함수다.

이를 이용해서 처음부터 끝까지 순열을 만들고 숫자로 바꾸면서 에라토스테네스의 체로 검사를 해주면 된다.

 

이런 함수가 있다는 걸 알았지만 dfs로 푸는게 좋지 않나 싶어서 재귀적으로 만드는 걸로 했다.

이것저것 체크할 게 많아져서 굉장히 귀찮아지지만... 일단 이렇다.

 

자세하게 어떻게 돌아가는지는 시간이 충분할 때 작성하겠다.

 

 

C++ 코드

---

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>

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;
}

void generatePermutations(const string& numbers, string current, vector<bool>& used, set<int>& primes) {
    if (!current.empty()) {
        int num = stoi(current);
        if (isPrime(num)) {
            primes.insert(num);
        }
    }
    
    for (int i = 0; i < numbers.size(); ++i) {
        if (!used[i]) {
            used[i] = true;
            generatePermutations(numbers, current + numbers[i], used, primes);
            used[i] = false;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    set<int> primes;
    vector<bool> used(numbers.size(), false);
    
    generatePermutations(numbers, "", used, primes);
    
    answer = primes.size();
    return answer;
}