[프로그래머스 LV2] - 소수 찾기(완전탐색) c++

문제

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

프로그래머스

접근방법

오래걸린 문제였다. 생각보다 어려워서 헤멨다.

 

푼 방법은 다음과 같다.

 

1. numbers 배열을 통해 나올 수 있는 가장 큰 숫자를 찾는다. (find_max)

2. 그 숫자까지 수 중 소수를 찾는다.(isprime)

3. 그 소수에 있는 숫자 하나하나 numbers에 있는 숫자에 모자라지 않고 포함되면 합격(check_possible)

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

bool isprime(int n) {
    if (n <= 1) return false; // 0 and 1 are not prime numbers
    if (n <= 3) return true;  // 2 and 3 are prime numbers

    // Check if n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0) return false;

    // Check for divisors of form 6k ± 1, up to sqrt(n)
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }

    return true;
}

bool check_possible(vector<int> cnt, string numbers) {
    vector<int> temp(10);
    for (char s : numbers) {
        temp[s - '0']++;
    }
    for (int i=0;i<10;i++) {
        if (cnt[i] > temp[i]) return false;
    }
    return true;
}
int find_max(string numbers) {
    vector<char> temp;
    for (char c : numbers) {
        temp.push_back(c);
    }
    sort(temp.begin(), temp.end(), greater<>());
    string s = "";
    for (int i=0;i<temp.size();i++) {
        s += temp[i];
    }
    return stoi(s);
}
//최고로 큰 숫자까지 소수들을 모두 검토
//그 숫자가 numbers의 숫자에 없다면 최소.
//그 숫자의 개수가 numbers에 모자라면 취소.
int solution(string numbers) {
    int answer = 0;
    int n = find_max(numbers);
    for (int i=2;i<=n;i++) {
        if (isprime(i)) {
            vector<int> cnt(10, 0);
            string temp = to_string(i);
            // cout << temp << " ";
            for (int j=0;j<temp.size();j++) {
                cnt[temp[j] - '0']++;
                // cout << temp[j] << " ";
            }
            // cout << endl;
            if (check_possible(cnt, numbers)) {
                answer++;
                // cout << "check" << endl;
            }
        }
    }
    
    return answer;
}

개선할 점

다른 사람 코드를 보니, 

next_permutation 함수와 set를 이용해 풀 수도 있었다.

 

next_permutation은 순열을 구해주는 함수다.