[프로그래머스] 완전탐색 - 소수찾기 / 순열, next_permutation

문제

 

풀이

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

vector<bool> visited;
set<int> ss;

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

void dfs(int len, string str, vector<string> v){
    if(str.length() == len) {
        //중복되는 값 없애기 위해 set 자료구조 사용
        ss.insert(stoi(str)); 
        return; 
    }
    
    for(int i=0; i<v.size(); i++){
        if(!visited[i]){
            visited[i] = true;
            string s = str + v[i];
            dfs(len,s,v);
            visited[i] = false;
        }
    }
    
    
}

int solution(string numbers) {
    int answer = 0;
    vector<string> v;
    for(int i=0; i<numbers.size(); i++){
        v.push_back(numbers.substr(i, 1));
    }
    
    //깊이탐색으로 모든 순열(중복) 구하기
    for(int i=1; i<=numbers.length(); i++){
        visited.assign(7, false);
        dfs(i, "", v);
    }
    
    //소수확인
    for(auto s : ss){
        if(sosu(s)) answer ++;
    }
    
    return answer;
}

자료구조 set을 활용하여 순서가 존재하지 않는 순열을 구한 후, 소수 판정해주었다. 

 

 

 

 

---

다른 사람 풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#define MAX 9999999999
using namespace std;

bool isPrime(int number)
{
    if (number == 1)
        return false;
    if (number == 2)
        return true;
    if (number % 2 == 0)
        return false;

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

    return isPrime;
}

bool compare(char a, char b)
{
    return a > b;
}

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

    string temp;
    temp = numbers;

    sort(temp.begin(), temp.end(),compare);

    vector<bool> prime(std::stoi(temp)+1);

    //cout << stoi(temp) << endl;
    prime[0] = false;
    for (long long i = 1; i < prime.size(); i++)
    {
        prime[i] = isPrime(i);
    }
    //cout << "chk1" << endl;
    //int num = std::stoi(numbers);

    string s, sub;

    s = numbers;

    sort(s.begin(), s.end());
    set<int> primes;
    int l = s.size();
    do {
        for (int i = 1; i <= l; i++)
        {
            sub = s.substr(0, i);
        //  cout << "chk2" <<  " " << sub<<  endl;
            if (prime[std::stoi(sub)])
            {
                primes.insert(std::stoi(sub));
            }
        }
    } while (next_permutation(s.begin(), s.end()));

    //cout << primes.size();
    answer = primes.size();
    return answer;
}

next_permutation을 통해 순열을 구할 수 있다.

 

next_permutation 

// default
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// custom
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

• #include <algorithm> 헤더파일이 필요하다.
• 순열을 구할 컨테이너의 시작과 끝 iterator를 인자로 받는다.
• next_permutation: 현재 나와 있는 수열에서 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면 false를 반환한다.
• prev_permutation: 현재 나와 있는 수열에서 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면 false를 반환한다.

 

next_permutation 의 주의사항

• 오름차순으로 정렬된 값을 가진 컨테이너로만 사용이 가능하다.
• default는 오름차순으로 순열을 생성한다.
• 중복이 있는 원소들은 중복을 제외하고 순열을 만들어준다.

 

---

https://twpower.github.io/82-next_permutation-and-prev_permutation

[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기

https://mjmjmj98.tistory.com/38

[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기