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

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

---

728x90

반응형

👩‍💻 코드

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

using namespace std;

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    
    return true;
}

int solution(string numbers) {
    set<int> primes;
    sort(numbers.begin(), numbers.end());

    do {
        for (int len = 1; len <= numbers.size(); len++) {
            int num = stoi(numbers.substr(0, len));
            
            if (isPrime(num)) {
                primes.insert(num);
            }
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

    return primes.size(); 
}

---

📝 풀이

next_permutation 함수를 이용하여 numbers의 모든 순열을 구합니다.

현재 순열에서 길이 1부터 numbers의 길이까지 숫자 문자열을 추출합니다.

추출한 숫자가 소수가 맞다면 set에 저장합니다.

set을 사용했기 때문에 중복된 숫자는 없습니다.

따라서 primes.size()를 return 합니다.