(프로그래머스 c++)소수 찾기

우선 numbers를 내림차순으로 정렬을 하도록 하였다.

그러면 numbers의 최대값이 나오고, int형으로 변환하여 max 변수에 저장하였다.

그리고 for문과 전역변수로 선언한 prime 배열을 이용하여 2 ~ max 사이에 있는 소수를 false로 바꿔주도록 한다.

(for문과 배열을 이용하여 소수 찾는 형태는 외워두면 알고리즘 문제에서 유용하게 쓸 수 있다..!)

for(int i = 2; i <= max; i++)
{
	for(int j = i + i; j <= max; j += i)
		prime[j] = true;
}

 

 

그리고 next_permutation 함수를 이용하였다.

next_permutation 함수는 수의 조합을 구할 수 있다.

자세한 사항은

https://twpower.github.io/90-combination-by-using-next_permutation

[Algorithm] C++에서 next_permutation을 이용해 조합(Combination) 구하기

do~while문에서 for문을 이용하여 number에 정렬되어 있는 수를 모두 탐색하여 소수인지 판별한다.

next_permutation이 자동으로 정렬을 해주니 for문을 통해 각 자리를 더하여 수를 만들어준다.

int형으로 변환을 시켜준 후 tmp에 저장,

tmp > 1 && prime[tmp] == false 인 경우는 소수가 맞으므로 answer++, prime[tmp] = false를 해준다.

 

계에에에속 돌다가 모든 조합이 만들어지면 끝이 나게 된다..!

일종의 DFS(?)라고 할 수 있을 것 같다..!

결국에는 모든 수를 조합하였으니..!

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
bool prime[10000000] = {false,};

int solution(string numbers) {
    int answer = 0;
    int max = 0;
    int tmp = 0;
    sort(numbers.begin(), numbers.end(), greater<int>());
    max = stoi(numbers);
    
    for(int i = 2; i <= max; i++)
    {
        for(int j = i + i; j <= max; j += i)
            prime[j] = true;
    }
    sort(numbers.begin(), numbers.end()); 
    
    do
    {
        string str = "";
        tmp = 0;
        for(int j = 0; j < numbers.size(); j++)
        {
            str += numbers[j];
            tmp = stoi(str);
            if(tmp > 1 && prime[tmp] == false)
            {
                answer++;
                prime[tmp] = true;
            }
        }
    }while(next_permutation(numbers.begin(),numbers.end()));

    
    return answer;
}