[Programmers/C++] 소수 찾기

1. 문제

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

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

제한사항

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

2. 풀이

문자열의 문자들을 각각 숫자로 변경하여 저장한다. 숫자를 오름차순으로 정렬하고 next_permutation 함수를 사용하여 가능한 모든 순열을 생성하고, 해당 순서로 생성할 수 있는 모든 숫자들을 생성한다. 이 후 오름차순으로 다시 정렬하고, 변수 내의 중복을 모두 제거한다. 마무리로 소수인 수의 갯수를 구하고 반환한다.

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

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

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

    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<int> num;
    vector<int> temp;
    int len = numbers.size();

    for (int i = 0; i < len; i++) {
        num.push_back(numbers[i] - '0');
    }

    sort(num.begin(), num.end());
    do {

        for (int i = 0; i <= len; i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp = tmp * 10 + num[j];
                temp.push_back(tmp);
            }
        }
    } while (next_permutation(num.begin(), num.end()));

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

    len = temp.size();

    for (int i = 0; i < len; i++) {
        if (isPrime(temp[i])) answer++;
    }

    return answer;
}

[참조]

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

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