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

문제 설명

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

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

제한사항

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

입출력 예

Solution

#include <algorithm>
#include <unordered_set>
#include <cmath>

using namespace std;

int isPrime(int N){
    if(N == 0 || N == 1) return 0;
    for(int i = 2; i <= sqrt(N); i++){
        if(N % i == 0) return 0;
    }
    return 1;
}

int solution(string numbers){
    unordered_set<int> uos;
    sort(numbers.begin(), numbers.end());
    do{
        for(int i = 1; i < numbers.size() + 1; i++){
            int x = stoi(numbers.substr(0, i));
            if(isPrime(x)) uos.insert(x);
        }
    }while(next_permutation(numbers.begin(), numbers.end())); 
    return uos.size();
}

간단하다. unordered_set과 next_permutation을 활용하면 된다.

int isPrime(int N){
    if(N == 0 || N == 1) return 0;
    for(int i = 2; i <= sqrt(N); i++){
        if(N % i == 0) return 0;
    }
    return 1;
}

우선 소수이냐 아니냐를 판별하는 함수는 설명을 생략하도록 하겠다. 너무 뻔하니까.

int solution(string numbers){
    unordered_set<int> uos;
    sort(numbers.begin(), numbers.end());
    do{
        for(int i = 1; i < numbers.size() + 1; i++){
            int x = stoi(numbers.substr(0, i));
            if(isPrime(x)) uos.insert(x);
        }
    }while(next_permutation(numbers.begin(), numbers.end())); 
    return uos.size();
}

우선 숫자들을 한번 정렬해준다. 그리고 각 숫자들을 가지고 말 그대로 순열을 뽑아서 돌려보는 것이다. 1개를 뽑는 경우, 1개부터 number 크기만큼, 예를 들면 카드가 4개라서 1234라는 input이 들어갔다면 1부터 4까지 일단 뽑아보는 것이다. 물론 next_permutation을 돌렸으니 numbers 내의 모든 가능한 경우의 수에서 그런 선택을 해 볼 수 있을 것이다.
그래서 그 값이 stoi를 통해 int형으로 변환시켰을 때 소수면 uordered_set에 집어넣는다. 그냥 set에 넣어도 크게 상관은 없을 것 같다만 딱히 순서가 필요하지 않으니까, 그리고 어쨌든 중복을 허용하지 않는다는 것은 똑같으니 set을 쓰든 unordered_set을 쓰든 크게 상관은 없다.

말 그대로 완전탐색이기 때문에 가능한 모든 수를 다 뒤져보면 된다. 그저 그 방식을 좀 더 고급지게 구현할 수 있느냐? 가 프로그래머의 실력을 조금 더 업그레이드 시킬 수 있지 않을까?