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

문제

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

코딩테스트 연습 - 소수 찾기

 

문제풀이

 

next_permutation과 unordered_set을 이용하여 풀었다.

문자열의 문자의 순서들을 서로 바꿔가며 소수가 몇개인지 찾는 문제이다.

에라토스테네스 체를 이용해서 소수를 미리 구해놓아야되나 싶었는데 숫자의 범위가 9,999,999까지라 매번 구했다.

 

next_permutation을 사용하기 위해 먼저 오름차순으로 숫자들을 정렬한다.

string형 수들을 int형으로 바꾸고 2부터 숫자의 제곱근까지 1씩 더해가면서 해당 수로 나눴을때 나머지가 0인지를 판별한다.

만약 나머지가 0이라면 소수가 아니므로 다음 조합으로 넘어간다.

만약 소수라면 unordered_set에 저장한다.

이런식으로 모든 조합을 확인한다.

 

마지막으로는 숫자가 0이거나 1인 경우가 있으면 erase를 하고 prime의 크기를 return 한다.

 

코드

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

unordered_set<int>prime;

int solution(string numbers) {

    sort(numbers.begin(), numbers.end());

    do {
        string s_num("");
        for (int idx = 0; idx < numbers.size(); ++idx) {
            s_num += numbers[idx];
            int num = stoi(s_num);
            if (prime.find(num) != prime.end()) continue;
            int mul = 2;
            for (mul = 2; mul * mul <= num; ++mul) {
                if (num % mul == 0) break;
            }
            if (mul * mul > num) prime.insert(num);
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

    if (prime.find(1) != prime.end()) prime.erase(1);
    if (prime.find(0) != prime.end()) prime.erase(0);

    return prime.size();
}