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

 

문제 설명

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

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

 

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

입출력 예

 

numbers	return
17	3
011	2

 

 

입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

 

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

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

using namespace std;

vector <int> vec;
vector <int> allCase;

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

int solution(string numbers) {
    int answer = 0;
    for (int i = 0; i < numbers.size(); i++) vec.push_back(numbers[i] - '0');
    sort(vec.begin(), vec.end());
    
    do {
        for (int i = 0; i <= vec.size(); i++) {
            int temp = 0;
            for (int j = 0; j < i; j++) {
                temp = (temp * 10) + vec[j];
                allCase.push_back(temp);
            }
        }
    } while (next_permutation(vec.begin(), vec.end()));
    
    sort(allCase.begin(), allCase.end());
    allCase.erase(unique(allCase.begin(), allCase.end()), allCase.end());
    
    for (int i = 0; i < allCase.size(); i++)
        if (decimal(allCase[i])) answer++;
    
    return answer;
}

 

---

next_permutation 함수를 이번 문제를 풀면서 처음 접해봤네요.

해당 함수를 알기 전에 순열을 먼저 알아보고 갑시다.

 

순열

순열(permutation)이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다.

 

예를 들어 집합 {1, 2, 3}의 원소들의 모든 순열을 구한다면

{1, 2, 3}

{1, 3, 2}

{2, 1, 3}

{2, 3, 1}

{3, 1, 2}

{3, 2, 1}

로 총 6가지가 나오게 됩니다.

 

해당 순열을 구해주는데 next_permutation 함수를 사용하는데 이에도 주의 사항이 있습니다.

 

1. 오름차순으로 정렬된 값을 가진 컨테이너로만 사용가능합니다.

2. default로 operator < 를 사용해 순열을 생성합니다. 즉 오름차순으로 순열을 생성합니다. 

3. 중복이 있는 원소들은 중복을 제외하고 순열을 만들어줍니다.

 

때문에 해당 함수를 통해 모든 경우를 뽑아낸 후, 벡터에 push 했습니다.