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

🍊 유사한 문제

본 문제와 비슷한 유형의 문제입니다. 문제가 어려웠거나 비슷한 유형의 문제를 풀어보고 싶다면 추천드립니다.

[프로그래머스 Level 2] 타겟 넘버

🖊️ 문제

소수 찾기  

 

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

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

 

제한사항

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

 

🖥️ 코드

#include <string>
#include <vector>
#include <math.h>
#include <set>

using namespace std;

bool visited[8];
set<int> s;

bool isPrime(int n)
{
    if (n == 1 || n == 0)
        return false;

    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;

    return true;
}

void DFS(int now, string str, string numbers)
{
    if (now == numbers.size())
    {
        if (str.empty())
            return;

        int target = stoi(str);
        if (isPrime(target))
            if (s.find(target) == s.end()) s.insert(target);

        return;
    }

    for (int i = 0; i < numbers.size(); i++)
    {
        if (visited[i])
            continue;

        visited[i] = true;
        DFS(now + 1, str, numbers);
        DFS(now + 1, str + numbers[i], numbers);
        visited[i] = false;
    }
}

int solution(string numbers)
{
    DFS(0, "", numbers);

    return s.size();
}

 

🤔 나의 생각

조합한 수가 소수인지는 판별하는 것보다 DFS를 사용해서 숫자의 조합을 만들어 내는 게 문제의 핵심 같다. 

숫자를 포함한다 또는 포함하지 않는다 분기하며 숫자의 모든 조합을 찾아 소수인지 판별하니 쉽게 통과했다!