[프로그래머스] 소수 찾기 c++(순열 구현)

순열을 구현하는 방법에 대해 공부할 수 있었던 문제. 

 

 

문제 설명

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

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

 

제한사항

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

문제 풀이

 

1. 순열 구현

vector<int> all_nums; // 중복되는 숫자를 걸러주는 class

//순열을 구현
string swap(string str, int depth, int i)
{
    char tmp = str[depth];
    str[depth] = str[i];
    str[i] = tmp;
    return str;
}

void permutation(string str, int depth, int n, int r)
{
    if (depth == r){
        all_nums.push_back(stoi(str.substr(0, r)));
        return;
    }
    
    for(int i = depth; i < n; i++) {
        str = swap(str, depth, i);
        permutation(str, depth + 1, n, r); 
        str = swap(str, depth, i);
    }
}

bool is_decimal(int num){
    for (int i=2; i<=sqrt(num); i++){
        if (num%i == 0) return false;
    }
    if(num<=1) return false;
    return true;
}

2. vector 내 중복값 제거

sort(all_nums.begin(), all_nums.end());
all_nums.erase(unique(all_nums.begin(), all_nums.end()), all_nums.end());

3. 소수 여부 판별

bool is_decimal(int num){
    for (int i=2; i<=sqrt(num); i++){
        if (num%i == 0) return false;
    }
    if(num<=1) return false;
    return true;
}

 

전체 풀이

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

using namespace std;

vector<int> all_nums; // 중복되는 숫자를 걸러주는 class

//순열을 구현
string swap(string str, int depth, int i)
{
    char tmp = str[depth];
    str[depth] = str[i];
    str[i] = tmp;
    return str;
}

void permutation(string str, int depth, int n, int r)
{
    if (depth == r){
        all_nums.push_back(stoi(str.substr(0, r)));
        return;
    }
    
    for(int i = depth; i < n; i++) {
        str = swap(str, depth, i);
        permutation(str, depth + 1, n, r); 
        str = swap(str, depth, i);
    }
}

bool is_decimal(int num){
    for (int i=2; i<=sqrt(num); i++){
        if (num%i == 0) return false;
    }
    if(num<=1) return false;
    return true;
}

int solution(string numbers) {
    int answer = 0;
    //1. 1 ~ numbers.length 자리의 숫자 조합을 생성한다.
    for (int i=1; i<=numbers.length(); i++){
        permutation(numbers, 0, numbers.length(), i);
    }
    //2. vector 중복 숫자 제거
    sort(all_nums.begin(), all_nums.end());
    all_nums.erase(unique(all_nums.begin(), all_nums.end()), all_nums.end());
    //3. 각 숫자가 소수인지 판별
    while(all_nums.size()!=0){
        int number = all_nums.back();
        all_nums.pop_back();
        if (is_decimal(number)) answer++;
    }
    
    return answer;
}