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

문제 :

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

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

 

제한 사항 :

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

입출력 예 :

numbers	return
"17"	3
"011"	2

 

코드 :

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
bool visited[8]={0,};
string str="",paper;
vector<int> nums;

bool isPrime(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;
}

void dfs(int num, int size) {
    if (num == size) {
        return;
    }
    for (int i = 0; i < size; i++) {
        if (!visited[i]) {
            visited[i] = true;
            str.push_back(paper[i]);
            nums.push_back(stoi(str));
            dfs(num+1, size);
            visited[i] = false;
            str.pop_back();
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    paper=numbers;
    dfs(0,paper.size());
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int j = 0; j < nums.size(); j++) {
        if (isPrime(nums[j])) answer++;
    }
    return answer;
}

 

다시 한번 짚고 넘어가기 :

-테스트 케이스 2,10,11번이 실패한 이유

소수인지 판별하는 isPrime함수에서 for문의 범위인 sqrt(n)을 포함 시키지 않았다.

 

-소수 판별할때 범위를 2~sqrt(n)으로 하여 빠르게 검색한다.

 

-조합문제일 경우에는 dfs를 사용하여 중복된 숫자를 고르지 않을 경우에는 bool visited 변수를 사용한다.