[프로그래머스] - 소수 찾기(C++)

프로그래머스

[문제 설명]

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

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

 

제한사항

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

입출력 예

 

numbers	return
"17"	3
"011"	2

 

입출력 예 설명

 

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

 

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

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

---

[문제 풀이]

주어진 숫자로 만들수 있는 숫자들 중 소수가 몇개 있는지 찾는 문제다.

numbers의 길이가 최대 7이므로 전체의 경우를 탐색해도 괜찮겠다는 생각이 들어 dfs로 모든 경우에 대해 찾기로 했다.

문제를 해결한 방식은 아래와 같다.

 

1. 우선 dfs로 모든 경우의 수를 찾는다.

1.1 std::set을 이용하여 중복되는 값을 제외한다.

1.2 찾을수 있는 모든 숫자중 가장 큰 숫자를 찾는다.

 

2. 1번 과정에서 찾은 가장 큰 숫자까지의 소수를 미리 찾아 놓고 배열에 저장해놓는다.

 

3. iterator를 이용해서 set을 순회하면서 저장된 숫자가 소수라면 answer값을 증가시킨다.

 

4. set을 모두 순회했다면 answer값을 리턴한다.

 

위의 과정에서 소수를 찾는 방법이나 순열을 구하는 방법에서 좀 더 효율적으로 개선하면 좀 더 좋은 코드가 되지 않을까 싶다.

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

 

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

#define INPUT_MAX 9999999
using namespace std;

vector<bool> primeChecker(INPUT_MAX+1, 0);
set<int> nums;
vector<bool> checked(8,0);
int maxNum = 0;

void PrimeCheckerSet(int num)
{
    primeChecker[0] = primeChecker[1] = 1;
    for(int i= 2; i <= num; i++)
    {
        if(primeChecker[i] == 1) continue;
        primeChecker[i] = 0;
        for(int j = i+i; j <= num; j+= i)
        {
            primeChecker[j] = 1;
        }
    }
}

bool isPrime(int num)
{
    return !primeChecker[num];
}

void dfs(string& numbers, string& cur_num, int target)
{
    if(cur_num.size() == target)
    {
        int temp_num = 0;
        for(int i =target-1; i >= 0 ; i--)
        {
            temp_num *= 10;
            temp_num += cur_num[i] - '0';
        }
        if(temp_num != 0) nums.insert(temp_num);
        if(temp_num > maxNum) maxNum = temp_num;
    }
    
    for(int i =0; i < numbers.size(); i++)
    {
        if(checked[i] == true) continue;
        checked[i] = true;
        cur_num.push_back(numbers[i]);
        dfs(numbers,cur_num, target);
        cur_num.pop_back();
        checked[i] = false;
    }
}

int solution(string numbers) {
    int numberSize = numbers.size();
    string cur_num = "";
    int answer = 0;

    for(int i =1; i <= numberSize; i++)
    {
        dfs(numbers,cur_num,i);  
    }
    PrimeCheckerSet(maxNum);
    for(const int& iter : nums)
    {
        if(isPrime(iter))
        {
            answer++;
        }
    }
    return answer;
}