[프로그래머스] 완전탐색 - 소수 찾기, C++

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

코딩테스트 연습 - 소수 찾기 | 프로그래머스

 본 문제는 The 2009 ACM North Western European Regional Contest Friedrich-Alexander-University, Nuremberg, Germany에서 출제된 A번 문제로 백준 3671번 산업 스파이의 편지와 동일한 문제다. 입력된 숫자를 통해 만들수 있는 소수의 개수를 구하는 문제다. 처음에 재귀함수를 이용하여 풀려고 도전하였으나, permutation을 이용하여 문제를 해결하였다. 코딩 과정은 다음과 같다.

1. permutation을 이용하여 모든 경우를 구한다.
2. vector의 erase와 unique를 이용하여 중복된 vector 값을 제외한다.
3. 주어진 vector 값의 소수 여부를 확인한다.

여기서 소수를 결정할 때, 여러가지 방법이 있지만 i의 제곱의 형태로 소수를 찾는것이 가장 빠르다. 또, 소수의 개수를 찾는 방법중 '에라토스테네스의 체'가 있는데 다음에 관련 문제를 풀었을 때 업로드하겠다. https://intaehwang.tistory.com/36

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool chk(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
 
int solution(string numbers) {
    int answer = 0;
    vector<int> v;
    for (int i = 0; i < numbers.size(); i++) {
        v.push_back(numbers[i] - '0');
    }
    sort(v.begin(), v.end());
    vector<int> ans;
    // 모든 경우의 수 찾기
    do {
        for (int i = 0; i <= v.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp = (tmp * 10) + v[j];
                ans.push_back(tmp);
            }
        }
    } while(next_permutation(v.begin(), v.end()));
    // 중복된 vector값 제외
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    // 소수 찾기
    for (int i = 0; i < ans.size(); i++) {
        if (chk(ans[i])) answer += 1;
    }
    return answer;
}