프로그래머스 Level2 소수 찾기

문제 설명

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

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

제한사항

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

입출력 예

입출력 예 설명

예제 #1[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

---

풀이 과정

먼저 소수를 찾는 문제이므로 소수있지 판단하는지 함수가 필요하다.

예전에 배운 에라스토테네스의 체를 이용했다. (이게 소수찾는데 가장 빠름)

bool isPrime(int n){
    if(n==0 || n==1){
        return false;
    }else{
        for(int i=2;i<=sqrt(n);i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }

}

그리고 나선 이제 문자열의 조합들을 구해봐야 한다.

next_permutation을 사용해서 나올 수 있는 모든 순열 조합을 구한다음에 다른 벡터에 쌓아두었다.

입력값이 문자열로 주어졌으므로 stoi를 사용해서 숫자 형태로 벡터에 담아두어야한다.

do{
        string str;
        for(int i=0;i<v.size();i++){
            str=str+v[i];
            v2.push_back(stoi(str));
        }
    }while(next_permutation(v.begin(),v.end()));

그런데, 이렇게 한 이후 중복된 값이 벡터에 들어가 있을 수 있다.

벡터에서 중복된 값을 제거하기 위해서 erase메서드를 사용할 수 있다.

이건 몰랐던건데 벡터에서 중복제거를 하는데 사용하면 유용하게 쓸 수 있을 것 같다.

v2.erase(unique(v2.begin(),v2.end()),v2.end());

그리고 이제 벡터에 담긴 각 수에 대하여 아까 만든 소수 판별 함수를 사용하여 소수인지 아닌지를 판단해주면 된다.

---

소스 코드

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

using namespace std;

bool isPrime(int n){
    if(n==0 || n==1){
        return false;
    }else{
        for(int i=2;i<=sqrt(n);i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }

}

int solution(string numbers) {
    int answer = 0;
    vector<char> v;
    vector<int> v2;
    for(int i=0;i<numbers.size();i++){
        v.push_back(numbers[i]);
    }
    sort(v.begin(),v.end());
    do{
        string str;
        for(int i=0;i<v.size();i++){
            str=str+v[i];

            v2.push_back(stoi(str));
        }

    }while(next_permutation(v.begin(),v.end()));
    sort(v2.begin(),v2.end());
    v2.erase(unique(v2.begin(),v2.end()),v2.end());
    for(int i=0;i<v2.size();i++){
        if(isPrime(v2[i])==true){
            answer++;
        }
    }
    return answer;
}