[프로그래머스 / Level 2] 소수 찾기 (C++)

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

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

numbers값을 가지고 만들 수 있는 모든 수를 만들고 그 수가 소수인지 판별하는 문제입니다.

 

문제 접근법

• 에라토스테네스의 채를 이용하여 소수 판별기를 만들어둔다.
• string numers를 각각의 숫자로 바꾸어 vector에 저장한다.
• next_permutation을 이용하여 주어진 숫자로 만들 수 있는 모든 순서를 구현하고 이를 통하여 해당하는 숫자의 순서로 만들 수 있는 모든 숫자를 만들어본다.
• 만든 값들을 set에 넣어 중복을 방지한다.
• set의 값들을 소수 판별기에 넣어 만들 수 있는 소수의 갯수를 파악한다.

아래는 코드입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
bool check[10000001];
 
int solution(string numbers) {
    int answer = 0;
    int len = numbers.size();
    check[0] = true;
    check[1] = true;
    
    for(int i = 2; i * i <= 10000000; i++)
    {
        if(!check[i])
        {
            for(int j = i * i; j <= 10000000; j += i)
            {
                check[j] = true;
            }
        }
    }
    
    vector<int> v(len);
    set<int> s;
    
    for(int i = 0; i < len; i++)
        v[i] = numbers[i] - '0';
    
    sort(v.begin(), v.end());
    
    do
    {
        for(int i = 1; i <= len; i++)
        {
            int temp = 0;
            
            for(int j = 0; j < i; j++)
            {
                temp = temp * 10 + v[j];
                s.insert(temp);
            }
        }
    }while(next_permutation(v.begin(), v.end()));
    
    for (auto au : s)
        if(!check[au])
            answer++;
    
    return answer;
}