프로그래머스[Lv.2] - 소수 찾기

문제 설명

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

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

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

프로그래머스

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

간단한 알고리즘 두 가지 정도를 합치면 풀 수 있는 문제이다.

우선 가장 핵심이 되는 부분은 아무래도 소수를 판별하는 것이다.

소수를 판별하기 위해서는 현재 알려진 알고리즘이 없다.

따라서, 2부터 나눠가면 나누어 떨어지는지 검사해야 한다.

하지만, 한 가지 최적화 방법이 있다. 

소수화 판별을 위해 2부터 n까지 나누어 떨어지는지 확인하는 과정에서 나누어 떨어지는 것에 초점을 두면 알 수 있다.

나누기 연산은 교환 법칙이 성립한다.

즉, n의 제곱근까지만 나누어도 이후의 숫자들은 교환 법칙에 의해 대응되는 작은 수와 나누는 것과 동일하게 적용된다.

따라서, n의 제곱근까지만 검사해도 된다는 것이다.

 

그리고 다른 한 가지 부분은 주어진 문자열로 숫자들을 만드는 것이다.

즉, 순열을 만드는 것인데 길이가 고정되어 있지 않다.

또한, 중복은 허용되지 않는다.

따라서, 순열과 부분 집합을 만드는 방법을 섞어 사용해야 한다.

계속하여 재귀를 진행하며 현재 idx의 수를 포함시킨 경우와 그렇지 않은 경우를 각각 진행한다.

재귀가 진행하여 depth가 주어진 문자열의 길이와 같아진다면 소수 여부를 판단하고 중복을 방지하기 위해 set을 이용하여 관리한다.

---

 

 

 

 

 

 

전체 코드

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

using namespace std;

bool isPrime(int n)
{
    if(n < 2) return false;
    bool flag = true;
    
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0) 
        {
            flag = false;
            break;
        }
    }
    
    return flag;
}

int makePer(string numbers, vector<int>& per, vector<bool>& checked, int num, int depth, int max, set<int>& results)
{
    if(depth == max)
    {
        if(results.find(num) != results.end()) return 0;
        
        cout << num << "\n";
        results.insert(num);
        if(isPrime(num)) return 1;
        return 0;
    }
    
    int cnt = 0;
    
    for(int i = 0; i < numbers.size(); i++)
    {
        if(checked[i]) continue;
        
        num *= 10;
        num += numbers[i]-'0';
        checked[i] = true;
        cnt += makePer(numbers, per, checked, num, depth+1, max, results);
        
        num /= 10;
        checked[i] = false;
        cnt += makePer(numbers, per, checked, num, depth+1, max, results);
    }
    
    return cnt;
}

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

    vector<int> temp;
    set<int> results;
    vector<bool> checked(numbers.size(), false);
    
    answer = makePer(numbers, temp, checked, 0, 0, numbers.size(), results);
    return answer;
}

---

 

 

 

 

 

ps

문제를 풀긴 했지만 시간 복잡도가 마음에 들지 않는다.

분명 더 좋은 방법이 있을 것이다.

현재는 모든 부분집합을 생성하며 중복 여부에 따라 제거하지만 중복을 만들지 않는 방법이 존재할 것이다.

---