프로그래머스. 소수 찾기

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

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

 

1. 주어진 숫자들을 1개 뽑는 조합, 2개 뽑는 조합, ... , 모두 뽑는 조합을 구한다.

주어진 숫자가 "17" 이라면

조합은 {1}, {7}, {17}

 

2. 구한 조합들에 대해 가능한 모든 순열을 구한다.

조합 {1} : 1

조합 {7} : 7

조합 {17} : 17, 71

 

3. 만들어진 순열이 소수인지 판단하고 소수가 맞다면 새로운 ans 벡터에 푸쉬한다. (중복검사 후)

 

4. ans 벡터의 크기가 답이다

 

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

using namespace std;

vector<int> ans;
int num;
bool mark[8];

// 전달받은 순열이 소수인지 판별
bool IsItPrime(vector<char> comb)
{
    bool isPrime = false;

    string str = "";
    for(int i = 0; i < comb.size(); i++)
    {
        str += comb[i];
    }

    // string to integer
    num = stoi(str);

    // 0,1은 소수가 아님
    if(num <= 1) return false;
    // 2,3은 소수
    if(num == 2 || num == 3) return true;
    // 2부터 num-1까지 중 나눠서 떨어지는 수가 있으면 소수가 아님
    for(int i = 2; i < num; i++)
    {
        if(num % i == 0)
        {
            return false;
        }
    }
    return true;
}

// 소수로 판별된 숫자가 ans 벡터에 없다면 푸쉬함
void PushToAns()
{
    bool duplicated = false;
    for(int i = 0; i < ans.size(); i++)
    {
        if(ans[i] == num)
        {
            duplicated = true;
            break;
        }
    }
    // 중복되지 않았다면 ans 벡터에 푸쉬
    if(!duplicated) ans.push_back(num);
}

int solution(string numbers) {
    int answer = 0;

    sort(numbers.begin(), numbers.end(), greater<>());

    for(int idx = 1; idx <= numbers.size(); idx++)
    {

        for(int i = 0; i < numbers.size(); i++)
        {
            if(i < idx) mark[i] = true;
            else mark[i] = false;
        }

        do {
            vector<char> comb;
            // 만들어진 조합을 comb 벡터에 푸쉬한다
            for(int i = 0; i < numbers.size(); i++)
            {
                if(mark[i]) comb.push_back(numbers[i]);
            }

            // 만들어진 조합으로 모든 순열을 구한다
            do {
                // 소수가 맞다면
                if(IsItPrime(comb))
                    PushToAns();

            }while(prev_permutation(comb.begin(), comb.end()));

        }while(prev_permutation(mark, mark+numbers.size()));

    }

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

 

---

다음날 다시 풀어봄.

 

다른 분들의 코드를 본 결과

가능한 모든 순열을 먼저 구하고 1개부터 n개 까지 뽑는 조합을 구하는것이 더 쉬운것 같다.

(이전에 내가 푼방식은 정반대였다, 조합을 구하고 그에따른 모든 순열을 구함)

 

그리고 unique와 erase를 이용해서 중복제거도 추가했다.

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


// 가능한 모든 수들이 들어감
vector<int> ans;

bool isPrime(int n)
{
    if(n < 2) return false;

    for(int i = 2; i < n; i++)
        if(n % i == 0)
            return false;


    return true;
}

int solution(string numbers) {
    int answer = 0;

    sort(numbers.begin(), numbers.end());

    do {
        string str = "";
        for(int i = 0; i < numbers.size(); i++)
        {
            str.push_back(numbers[i]);
            ans.push_back(stoi(str));
        }

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

    // 중복 제거
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    for(int i = 0; i < ans.size(); i++)
    {
        if(isPrime(ans[i]))
            answer++;
    }

    return answer;
}