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

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

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

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

입출력 예)

numbers	return
17	3
011	2

풀이)

내가 한 코드에서 무엇을 수정할 수 있을 지 적어보겠다.

1. 순열을 이용해서 나올 수 있는 모든 수를 확인했다.

   순열은 재귀방식을 통해 구했는데, vector의 next_permutation()함수를 통해 쉽게 구하는 법도 있다.

   numbers의 각 char를 임의의 vector에 넣고, 그 vector를 next_permutation을 이용해서 char들의 순열을 구하는 법

  

2. 순열을 통해 나올 수 있는 수를 구하다보면 중복된 수가 나올 수 있다.

   나올 수 있는 수가 0~9,999,999이니깐 중복 체크해주는 num[10000000] 배열을 두었다.

   이는 set 구조를 이용해도 된다.

   set <string> num을 선언해놓고, if(num.find(순열로 만들어진 string) == num.end())이면 새로운 수라는 것.

3. 구한 수가 n일때 소수인지 체크할때 for문을 2부터 n -1까지 다 돌렸는데,

   그럴 필요 없이 2부터 sqrt(n)까지만 돌리면 된다.

$$\sqrt n

코드)

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

int answer = 0;
bool visited[7];
bool num[10000000];
void dfs(int idx,string s,string numbers){
    if(s != ""){
        int temp = stoi(s);
        if(num[temp] == false){
            num[temp] = true;
            // cout << temp << endl;
            bool check = true;
            for(int i=2;i<temp;i++){
                if((temp % i) == 0){
                    check = false;
                    break;
                }
            }
            if(check && temp > 1) answer++;
        }   
    }

    for(int i = 0;i<numbers.size();i++){
         if(visited[i])continue;
        visited[i] = true;
        dfs(i+1,s+numbers[i],numbers);
        visited[i] = false;
    }
}

int solution(string numbers) {

    dfs(0,"",numbers);
    return answer;
}