프로그래머스 LV.2 소수 찾기

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

 

제한사항은 다음과 같다.

 

 

예시로 1과 7의 숫자 카드가 주어지면,

7하나 17하나, 71 이렇게 총 3개의 소수를 만들 수 있다.

 

마찬가지로

0, 1, 1 의 숫자카드로는

11, 101 이렇게 2개의 소수를 만들 수 있다.

 

그럼 이 문제를 어떻게 접근할 것인가?

 

1. 재귀함수를 활용하는 방법

2. 반복문을 활용하는 방법

 

1. 재귀함수를 활용하는 방법

재귀를 활용하면 다음과 같은 과정을 거친다.

 

1.  재귀를 통해 모든 숫자 조합을 하나씩 만들어준다
2.  STL의 set을 사용해서 중복되는 조합을 제거해준다.
3.  지금 만들어진 숫자가 소수인지 판별한다.

 

이렇듯 소수인지 아닌지 판단하고 싶을 때

가장 기본적으로 에라토스의 체를 사용할 수 있다.

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

using namespace std;
set<int> numberSet;


void recursive(string comb, string others) {
    if (comb != "") {
        numberSet.insert(stoi(comb));
    }


    for (int i = 0; i < others.size(); i++) {
        recursive(comb + others[i], others.substr(0, 1) + others.substr(i+1));
    }
}

bool IsPrime(int num) {
    if (num == 0 || num == 1) return false;

    int lim = sqrt(num);
    for (int i = 2; i <= lim; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int solution(string numbers) {

    int answer = 0;

    recursive("", numbers);


    for (int number : numberSet)
        if (IsPrime(number))
            answer++;

    return answer;
}

 

시간 초과가 뜬다.

 

 

2. 반복문을 활용하는 방법

 

아무래도 재귀함수는 시간이 좀 느리다.

함수를 타고 들어가야 하기 때문이다.

 

그럼 시간을 줄이기 위해 반복문을 활용해보자.

 

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

using namespace std;


bool IsPrime(int num) {
    // 0 과 1은 소수가 아님
    if (num < 2) return false;

    // 에라토스의 체
    int lim = sqrt(num);
    for (int i = 2; i <= lim; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int solution(string numbers) {
    set<int> numberSet;

    sort(numbers.begin(), numbers.end());

    // 모든 숫자 조합을 만들어 소수의 개수를 샌다.
    do {
        for (int i = 0; i < numbers.size(); i++) {
            if (IsPrime(stoi(numbers.substr(0, i + 1))))
                numberSet.insert(stoi(numbers.substr(0, i + 1)));
        }
        // 집합의 원소 조합에 대한 모든 경우의 수를 구한다.
    } while (next_permutation(numbers.begin(), numbers.end()));

    // 소수의 개수를 반환한다.
    return numberSet.size();
}

 

 

실행 결과