[프로그래머스] 소수 찾기

목차

• 문제 내용
• 나의 생각
• 전체 코드
• 테스트 코드

문제 내용

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
17	3
011	2

나의 생각

1. 소수를 구하는 방법? 에라토스테네스의 체를 이용합니다.

에라토스테네스의 체에 관하여 궁금하신 분은 아래 링크를 확인하고 오시면 감사하겠습니다.

에라토스테네스의 체란? (feat.cpp 구현)

소수 란? 1과 자기 자신을 제외한 나누어지는 수가 없는 수를 말합니다. 그렇게 되면 2를 제외한 모든 짝수는 소수가 될 수 없습니다. (짝수들은 2로 나누어 떨어지기 때문입니다.) bool check_the_prime_number(i..

coderb.tistory.com

2. 어느 숫자까지의 소수를 구해야 할까? 문자열로 만들 수 있는 최댓값까지 구합니다.(sort)

void solution(string numbers){
    // numbers 문자열 최댓값으로 만들기
    sort(numbers.begin(), numbers().end(), greater<int> ());
}

3. 문자열 조합은 어떻게 만들어 낼가? next_permutation()을 사용한다.

4. 중복되는 값은 어떻게 처리할까? set()을 사용하여 저장한다(set은 중복된 값을 허용하지 않는다.)

set <int> prime_tree;
sort(numbers.begin(), numbers.end());

do{
    for(int i = 1; i <= numbers.size(); ++i){
        string tmp = numbers.substr(0, i);
        if(!prime_number[stoi(tmp)])
            prime_tree.insert(stoi(tmp));
    }
}while(next_permutation(numbers.begin(), numbers.end()));

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

// 에라토스테네스의 체 알고리즘
void eratothenes(vector <bool> & prime_numbers){
    prime_numbers[0] = true;
    prime_numbers[1] = true;

    for(int i = 2; i < sqrt(prime_numbers.size()); ++i){
        if(!prime_numbers[i]){
            for(int j = i * 2; j < prime_numbers.size(); j+=i){
                prime_numbers[j] = true;
            }
        }
    }
}

int solution(string numbers){
    int answer = 0;
    // 큰수 만들기
    sort(numbers.begin(), numbers.end(), greater<int>());
    vector <bool> prime_numbers(stoi(numbers) + 1, false);
    eratothenes(prime_numbers);

    set <int> prime_tree;

    sort(numbers.begin(), numbers.end());
    do{
        for(int i = 1; i <= numbers.size(); ++i){
            string tmp = numbers.substr(0, i);
            if(!prime_numbers[stoi(tmp)])
                prime_tree.insert(stoi(tmp));
        }
    }while(next_permutation(numbers.begin(), numbers.end()));

    answer = prime_tree.size();
    return answer;
}

테스트 코드(필요하신분 만)

int main()
{
    const vector<string> numbers_testcases = {"17", "011"};

    for (int i = 0; i < numbers_testcases.size(); ++i)
    {
        const int ret = solution(numbers_testcases[i]);
        cout << ret << endl;
    }
    return 0;
}