프로그래머스 소수찾기c++ (완전탐색)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

문제 설명

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

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

제한사항

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

입출력 예

입출력 예 설명

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

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

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

풀이

예제 2를 예로 들면

"011"로 만들 수 있는 모든 수를 소수인지 체크하고 소수인 경우는 set에 추가해 준다.

set은 중복되는 소수를 제거해 준다.

 

"011"로 만들 수 있는 수

0

1

1

01

10

01

10

11

11

011

011

101

110

101

110

의 수들을 모두 소수인지 체크한다.

 

11

11

011

011

101

101

총 6개의 소수가 나오고, 이들을 set에 넣어 중복을 제거하면

11,101이 set에 저장된다.

set의 size를 출력하면 끝!

코드

#include <string>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
set<int> se;
bool check[7];
string st_num="";
void sosu(int num){
    if(num==1||num==0)
        return;

    for(int i=2; i*i<=num;i++){
        if(num%i==0){
            return;
        }
    }
    se.insert(num);
}

void permutation(string numbers, int start, int end){
    if(start==end){
        sosu(stoi(st_num));
        return;
    }
    for(int i=0; i<numbers.length();i++){
        if(check[i])
            continue;
        check[i]=true;
        st_num+=numbers[i];
        permutation(numbers,start+1,end);
        check[i]=false;
        st_num.pop_back();
    }
}

int solution(string numbers) {
    int answer = 0;

    for(int i=0; i<numbers.length();i++){
          sosu(numbers[i]-'0');
        if(i!=0)
            permutation(numbers,0,i+1);
    }
    answer = se.size();

    return answer;
}