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

 

 

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

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

 

numbers를 내림차순으로 정렬하고

 

그 수까지 is_prime 함수를 통해 소수 여부를 다 v에 넣어놓는다

 

이때 소수가 아니면 -1, 소수이면 1로 넣어놓고

 

이후 next_permutation으로 다시 오름차순으로 정렬된 numbers를 돌면서

 

소수가 아니고 체크가 됐으면 0, 소수고 체크 됐으면 2로 v 값을 바꿔준다. (answers 중복 체크를 제거하기 위해)

 

이때 "소수고 체크 됐으면 2로 v 값을 바꿔준다" 부분에서 answer를 +1 해준다.

 

 

Code

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

using namespace std;

int is_prime(int num) {
    if(num == 0 || num == 1) return -1;
    if(num == 2) return 1;
    
    for(int i=2; i<=sqrt(num); i++) {
        if(num%i==0) {
            return -1;
        }
    }
    return 1;
}

bool desc(int a, int b) {
    return a>b;
}

int solution(string numbers) {
    int answer = 0;
    vector<int> v;
    
    sort(numbers.begin(), numbers.end(), desc);
    
    // 소수가 아니면 -1, 소수이면 1, 소수가 아니고 체크가 됐으면 0, 소수고 체크 됐으면 2 
    for(long long i=0; i<=stoi(numbers); i++) {
        v.push_back(is_prime(i));
    }
    
    sort(numbers.begin(), numbers.end());
    
    do {
        for(int i=1; i<=numbers.size(); i++) {
            string tmp = numbers.substr(0, i);
            long long idx = stoi(tmp);
            
            if(v[idx]==-1) v[idx] = 0;
            else if(v[idx]==1) {
                v[idx] = 2;
                answer++;
            }
            else continue;
        }
        
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return answer;
}