👓 문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
입출력 예
numbers return "17" 3 "011" 2 입출력 예 설명
예제 1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.예제 2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
💣 제한 사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
🚨 접근 방법
문자열로 주어지며 각 문자는 0~9에 숫자에 해당한다.
이는 주어진 문자에 대해 순열을 이용하여 만들 수 있는 모든 수를 구해야한다.
모든 수를 구한 후 각 수에 대해 소수인지 판단하여 개수를 구한다.
전역 변수로 현재 수를 저장할 char 배열을 선언하고 각 인덱스 마다 현재 숫자를 추가한다.
재귀함수를 통해 현재 깊이에 해당하는 depth를 인덱스로 numbers 문자열의 숫자를 저장한다.
현재 뽑고자 하는 수의 길이에 해당하면 set 컨테이너에 그 수를 저장한다.
🚈 코드
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
// 소수? -> 1과 자기 자신을 제외한 약수가 존재하지 않는 자연수
char temp_num[8];
set<int> all_numbers;
vector<bool> check;
int cur_length;
bool func(int num){
// 0,1일 때는 확인 x
if(num<2){
return false;
}
int n=2;
while(n<num){
if(num%n==0){
return false;
}
n++;
}
// 자기자신 -1 까지 나누어 떨어지는 수가 없으면 소수 판단 -> true 반환
return true;
}
void permu(string numbers,int depth){
if(depth==cur_length){
if(temp_num[0]!='0'){
all_numbers.insert(stoi(temp_num));
}
return;
}
for(int i=0;i<numbers.length();i++){
if(!check[i]){
check[i]=true;
temp_num[depth]=numbers[i];
permu(numbers, depth+1);
check[i]=false;
}
}
}
// 1. 소수 판단 함수 만들기
// 2. numbers 문자열에서 만들 수 있는 모든 수 만들기
// 2-1. 순열을 이용해서 만들 수 있는 수를 저장하기
int solution(string numbers) {
int answer = 0;
for(int i=0;i<numbers.length();i++){
check.push_back(false);
}
for(int i=0;i<numbers.length();i++){
cur_length++;
permu(numbers, 0);
for(int j=0;j<check.size();j++){
check[j]=false;
}
}
for(auto p:all_numbers){
if(func(p))answer++;
}
return answer;
}