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

[문제 출처]

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

1. 문제

설명

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

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

 

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

 

2. 설명

 먼저 흩어진 종이조각을 붙여 숫자로 만들기 위해서는 dfs를 쓸수 있어야하는데 bfs만 알아서 공부를 해보았습니다. 많이 쓰이는 두가지 경우 모두 해보았습니다.

 

순서가 다르면 다르다고 치는 순열을 구현한것은 아래코드입니다.

bool visited[5];
string numbers;
string str = "";
vector <string> v;

void dfs(int cnt, int end) {
    if (cnt == end) 
        cout << str<<"\n";
   
    for (int i = 0; i < numbers.size(); i++) {
        if (visited[i] == 1)
            continue;

        visited[i] = 1;
        str += numbers[i];
        dfs(cnt + 1, end);
        visited[i] = 0;
        str.pop_back();
    }
}

int main() {
    string s="";
    numbers = "1231";
    dfs(0,4);
	return 0;
}

 

뽑는 순서는 중요하지 않고 항목이 중복되지 않게 뽑는것은 현재위치를 표시하는 point를 추가하면 되었습니다.

void dfs(int cnt, int end, int point) {
    if (cnt == end) 
        cout << str<<" ";
   
    for (int i = point; i < numbers.size(); i++) {
        if (visited[i] == 1)
            continue;

        visited[i] = 1;
        str += numbers[i];
        dfs(cnt + 1, end,point+1);
        visited[i] = 0;
        str.pop_back();
    }
}

int main() {
    string s="";
    numbers = "1234";
    dfs(0,3,0);
	return 0;
}

 이것을 통해 숫자들을 구한후 소수판별은 가장 큰숫자까지의 에라토스테네스의 체를 한뒤, 개수 세는것은 에러토스테네스의 체의 값들중 0인것을 ++해서 구해주었습니다.

 

3. 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;


void dfs(int cnt, int end, set<int>&num, vector<bool> &visited, string &s, string numbers) {
    if(cnt==end){
        num.insert(stoi(s));
        return;
    }
    
    for(int i=0; i<numbers.size(); i++){
        if(visited[i]==1)
            continue;
        visited[i]=1;
        s+=numbers[i];
        dfs(cnt+1,end,num,visited,s,numbers);
        visited[i]=0;
        s.pop_back();
    }
}


int solution(string numbers) {
    int answer = 0;
    
    vector<bool> visited(numbers.size(),0);
    set<int>num; // 만든 숫자담을것
    set<int>::iterator itr;
    string s; //dfs숫자담을것   
    
    // 모든숫자 만들기(중복 제외)
    for(int i=1; i<=numbers.size(); i++)
        dfs(0,i,num,visited,s,numbers);
    
   
    //에라토스테네스의 체
    int max_num=*(--num.end());
    vector<bool>find_sosu((max_num)+1, 0);
    for(int i=2; i*i<=max_num; i++){
        if(find_sosu[i]==0){
           for(int j=i*i; j<=max_num; j+=i)
               find_sosu[j]=1;
        }
    }
    find_sosu[0]=1; //0,1 소수 아닌것 추가
    find_sosu[1]=1;
    
    
    // 소수인것 찾기
    for(itr=num.begin(); itr!=num.end(); itr++){
        if(find_sosu[*itr]==0){
            answer++;
        }
    }
    
    return answer;
}