소수 찾기 - 프로그래머스, c++

 

 

- 문제 풀이

"완전 탐색"을 사용하는 문제였다.

순열 함수로 만든 모든 조합의 숫자들을 for문을 통해 소수인지 아닌지 판별하면된다.

+ 주어진 숫자로 만들 수 있는

   모든 종류의 순열을 만들어주는 함수는 #include <algorithm> next_permutation() 이고,

   모든 종류의 조합을 만들어주는 함수는 직접 만들어야 한다.

여기서는 조합을 만들어주는 함수를 사용해야 하므로 따로 함수 선언해주어야 한다.

 

 

- 코드

내가 작성해 제출한 코드는 다음과 같으나 성공하지 못했다.

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int solution(string numbers) {
    
    //필요한 변수 선언
    int answer = 0;
    vector<int> num(numbers.length());
    vector<int> temp;
    
    // 숫자를 하나씩 vector num에 저장해 오름차순 정렬
    for(int i=0; i<numbers.length(); i++) {
        num.push_back(static_cast<int>(numbers[i]));
    }
    sort(num.begin(), num.end());
    
    //모든 조합으로 숫자 만들어 만든 조합을 vector temp에 저장
    do{
        int n = num[num.size()-1];
        int t = 1;
        for(int i=num.size()-2; i>=0; i--) {
            n += num[i]*pow(10,t);
            t++;
        }
        temp.push_back(n);
    }
    while(next_permutation(num.begin(), num.end()));
    
    //만든 num이 소수인지 판별
    for(int i=0; i<temp.size(); i++) {
        bool p = false;
        for(int j=2; j*j<temp[i]; j++) {
            if(temp[i] % j == 0) {
                p = true;
            }               
        }
        if(!p)
            answer++;
    }
    
    return answer;
}

 

 

수정해 제출한 코드는 다음과 같다.

1. 해당 숫자가 소수인지 아닌지 판별하는 함수

2. 주어진 숫자로 만들 수 있는 모든 조합의 숫자를 만들어주는 함수(조합, combination)

3. 1, 2를 실행할 함수

    → 2번 함수를 실행해 만들 수 있는 숫자를 모두 만들어 저장

    → 위에서 만든 숫자들에 1번 함수를 실행해 소수인지 아닌지 판별

    → 소수의 개수 count해 반환하기 

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

using namespace std;

set<int> numberSet;

bool isPrime(int number)
{
    // 1. 0과 1은 소수가 아니다 (소수의 정의)
    if (number == 0 || number == 1)
        return false;

    // 2. 에라토스테네스의 체
    int lim = sqrt(number);
    for (int i = 2; i <= lim; i++)
        if (number % i == 0)
            return false;

    return true;
}

void makeCombination(string comb, string others)
{
    // 1. 현 조합을 numberSet에 추가한다.
    if (comb != "")
        numberSet.insert(stoi(comb));

    // 2. 현 조합 + others[i]를 조합하여 새로운 조합을 만든다.
    for (int i = 0; i < others.size(); i++)
        makeCombination(comb + others[i], others.substr(0, i) + others.substr(i + 1));
}

int solution(string numbers)
{
    // 1. 모든 숫자 조합을 만든다
    makeCombination("", numbers);

    // 2. 소수의 개수를 센다
    int answer = 0;
    for (int number : numberSet)
        if (isPrime(number))
            answer++;

    // 3. 소수의 개수를 반환한다.
    return answer;
}

(코드 참고: https://coding-grandpa.tistory.com/91)