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

 

문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다.

소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다.

우리는 두 가지 경우로 풀 수 있다.

dfs로 풀던가 next_permutation으로 풀던가 둘 중 하나로 풀면 된다.

나는 next_permutation으로 풀었다.

 

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

vector<bool> sieve;

void era(int n) {
    sieve.resize(n + 1, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (int j = i * 2; j <= n; j += i) sieve[j] = false;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end(), greater<int>());
    era(stoi(numbers));
    sort(numbers.begin(), numbers.end());
    
    set<int> ans;
    vector<int> ar;
    for (auto i : numbers) ar.push_back(i - '0');
    
    do {
        for (int i = 0; i <= ar.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp = (tmp * 10) + ar[j];
            }
            ans.insert(tmp);
        }
    } while (next_permutation(ar.begin(), ar.end()));
    
    for (auto i : ans) if (sieve[i]) answer++;
    
    return answer;
}

 

문자열의 길이가 7자리니 9,999,999 즉 10,000,000까지 배열을 생성해두면 편하다

나는 문자열을 받아서 내림차순으로 정렬하고 이후 에라토스테네스의 체에 넣어줬다.

이후 다시 정렬해주는 게 중요하다.

 

    do {
        for (int i = 0; i <= ar.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp = (tmp * 10) + ar[j];
            }
            ans.insert(tmp);
        }
    } while (next_permutation(ar.begin(), ar.end()));

 

next_permutation에서 모든 경우의 수를 따져보려면 벡터가 오름차순으로 정렬되어 있어야 한다.

예를 들어서 7, 1 이 벡터에 들어있다면 나오는 경우의 수는 7, 71 밖에 없지만

1, 7로 정렬되어있다면 0, 1, 7, 17, 71로 5개가 나온다.

 

또한 set을 통해 입력받으면 중복을 알아서 걸러주지만 vector로 하는 게 시간 복잡도면에서는 더 짧다.

 

ans.insert 대신 vector에 입력받고 정렬 후 중복 제거해주는 게 더 짧게 나왔다.