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

문제 설명

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

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

 

제한 조건

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

 

입출력 예

numbers	return
"17"	3
"011"	2

 

 

코드

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

using namespace std;
 
int is_prime(int n) {
    int i;
    
    if (n < 2)
        return 0;
    for (i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return 0;
    }
    return 1;
}
 
int solution(string numbers) {
    int answer = 0;
    int i;
    int j;
    int tmp;
    vector<int> num;
    vector<int> n;
    
    for (i = 0; i < numbers.size(); i++)
    {
        num.push_back(numbers[i] - '0');
    }
    sort(num.begin(), num.end());
    do {
        for (i = 1; i <= num.size(); i++)
        {
            tmp = 0;
            for (j = 0; j < i; j++)
            {
                tmp = (tmp * 10) + num[j];
            }
            n.push_back(tmp);
        }
    } while (next_permutation(num.begin(), num.end()));
    sort(n.begin(), n.end());
    n.erase(unique(n.begin(), n.end()), n.end());
    for (i = 0; i < n.size(); i++) {
        answer += is_prime(n[i]);
    }

    return answer;
}

 

주어진 숫자를 포함하는 문자열 numbers를 오름차순으로 정렬하여 가능한 모든 순열을 구한다. 각 순열에 대해 앞에서부터 (1 ~ n) 개의 숫자를 선택해 tmp를 만들어 n에 저장한다. n에서 중복을 제거하고 각 숫자에 대해 소수인지 검사하여 answer를 갱신한다.

 

링크

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

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

github.com/inbdni/Programmers/blob/master/level02/%EC%86%8C%EC%88%98%EC%B0%BE%EA%B8%B0.cpp

inbdni/Programmers