[프로그래머스] 코딩테스트 연습 > 완전탐색 > 소수 찾기(C++)

(1) 문제

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

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

---

(2) 제한사항

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

---

(3) 코드

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

using namespace std;

bool isPrime(int n);

int solution(string numbers) {
    int answer = 0;
    vector<int> number;
    string str_temp = "";

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

    do
    {
        for (int i = 0; i < numbers.size(); i++)
        {
            for (int j = 0; j < numbers.size() - i; j++)
            {
                str_temp += numbers.at(j);
            }
            number.push_back(stoi(str_temp));
            str_temp = "";
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

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

    for (int i = 0; i < number.size(); i++)
    {
        if (!isPrime(number.at(i)))
        {
            number.erase(number.begin() + i);
            i--;
        }
    }

    answer = number.size();

    return answer;
}

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

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

    return true;
}

---

(4) 실행결과

---