[프로그래머스] 소수 찾기 - 완전 탐색, 재귀, 소수 판별법

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

소수 찾기(링크)

풀이

주어지는 숫자 문자열의 숫자들 각각에 대해 사용하거나 사용하지 않은 경우로 정답 후보를 만들어 소수 판별을 진행한다. 재귀 함수의 입력으로 숫자 문자열을 받으면 앞에서 숫자를 하나 떼어내 소수 후보 문자열에 이어 붙여 소수인지 판별하고, 정답 후보에 추가된 숫자를 제외한 나머지 숫자 문자열로 함수를 재귀 호출한다.

디버깅

"011" 과 "11" 은 다른 문자열이므로 별개의 경우로 판단하지만 사실 같은 소수인 11이다. 다음과 같이 정수 변환 후 비교해 같은 경우로 판단했다.

 

if (stoi(candidate) == stoi(answers[i]))

개선한 코드

소수 판별을 아무 생각없이 목표 숫자의 절반까지의 자연수로 모두 나눴다. 소수 판별은 목표 숫자의 제곱근까지만 나누어 보면 확인할 수 있다. (에라토스테네스의 체 라는 소수 판별 알고리즘을 사용하면 더 빠르다.)

 

제곱근까지만 확인하는 이유를 어떤 n 이 소수인지 판별하며 증명해보자. n 이 합성수라 가정하면 n 은 1 과 n 사이 두 인수의 곱이다. n = sqrt(n) * sqrt(n) 이므로 n 을 이루는 인수 중 적어도 하나는 sqrt(n) 보다 작거나 같아야 한다. (둘 다 sqrt(n) 보다 크면 n 보다 커지므로 모순이다.) 

 

따라서, sqrt(n) 까지의 숫자 중에서 인수를 찾을 수 없다면 1 과 n 사이 인수들의 곱으로 n 을 만들 수 없으므로 n 은 합성수가 아니다. (즉, n 은 소수이다.)

C++ 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
using namespace std;

bool isPrimeNumber(string number) {
    int num = stoi(number);

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

int makePrimeNumber(string numbers, string candidate, vector<string>& answers) {
    // Nothing left to pick.
    if (numbers.length() == 0) return answers.size();

    int ret = 0;
    char number;

	for (int i = 0; i < numbers.length(); ++i) {
        number = numbers[i];
        candidate.append(1, number);
        numbers.erase(i, 1);

        if (isPrimeNumber(candidate) == true) {
            bool isNew = true;
            for (int i = 0; i < answers.size(); ++i) {
                if (stoi(candidate) == stoi(answers[i])) {
                    isNew = false;
                    break;
                }
            }
            if (isNew == true) answers.push_back(candidate);
        }

        ret = makePrimeNumber(numbers, candidate, answers);
        candidate.pop_back();
        numbers.insert(i, 1, number);
    }

    return ret;
}

int solution(string numbers) {
    int ret;
    string candidate = "";
    vector<string> answers;
    //set<int> answers;
    ret = makePrimeNumber(numbers, candidate, answers);
    return ret;
}