JArchive 프로그래밍 일기

문제

소수 찾기 프로그래머스 level2

리뷰

완전탐색 카테고리의 문제다.

에라토스테네스의 체로 소수를 체크해야 하고. 주어진 숫자들로 순열을 만들면 된다.

핵심 코드

bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

1. 예를 들어 71까지의 소수를 구하려면 72 크기의 배열을 만든다.소수의 배수들은 소수가 아니기 때문이다.
   에라토스테네스 GIF를 참고하자
2. 소수를 만날 때 마다 (인덱스 값이 true 라면, ) 소수의 배수가 되는 인덱스들의 값을 전부 false로 만든다.
3. 구하려는 범위 만큼 bool 배열을 만들고, 배열의 인덱스를 전부 소수라고 생각하여 true로 초기화 한다.

순열 만들기오름차순으로 정렬되어 있다면, 예를 들어 대상 벡터가 [1, 2, 3] 이라면, [3, 2, 1] 이 될 때 까지 순열을 만들어서 리턴해준다.

2. 따라서 반드시 미리 오름차순 정렬이 되어 있어야 한다. [3, 2, 1] 인채로 넣으면 바로 종료된다.
3. #include <algorithm>
next_permutation(v.begin(), v.end())

코드

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


bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

int solution(string numbers) {

    sort(numbers.begin(), numbers.end(), greater<int>()); 
    // 내림차순 정렬 -> 숫자로 만들 수 있는 가장 큰 수 만들기.

    int maxnum = atoi(numbers.c_str()); // 문자열->숫자

    eratos(maxnum); // 소수 체크

    sort(numbers.begin(), numbers.end()); // 오름차순 정렬 (next_permutation 함수 활용을 위함.)

    set<int> answer_set; // 유효한 숫자를 중복없이 저장하기 위한 set

    do{
        // substr로 1자리 숫자 부터 확인 
        for(int i = 1; i <= numbers.size(); i++){
            int temp_num = stoi( numbers.substr(0, i) );
            if(prime[temp_num]){
                answer_set.insert(temp_num); // set에 넣어서 중복제거 
            }
        } 

    }while( next_permutation(numbers.begin(), numbers.end()) ); 

    return answer_set.size();
}