level 2 소수찾기 -순열 (algorithm :: next_permutaion)

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

코딩테스트 연습 - 소수 찾기

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

using namespace std;

vector <int> v;
vector <int> choice;
vector <int> answer;

bool visit[8];


bool prime(int num) {

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


void DFS (int cnt, int target_num) {

    if(cnt == target_num) 
    {
        int ret = choice[0];
        for(int i=1; i<choice.size(); i++) {
            ret *= 10;
            ret += choice[i];
        }
        answer.push_back(ret);
        return;
    }
    
    for(int i=0; i<v.size(); i++) {
        if(visit[i] == true) continue;
        
        visit[i] = true;
        choice.push_back(v[i]);
        DFS(cnt+1, target_num);
        visit[i] = false;
        choice.pop_back();
    }
    
}


int solution(string numbers) {
    
    int number = stoi(numbers);
    
    while(number != 0) {
        v.push_back(number % 10);
        number = number / 10;
    }
    // for 0
    while(v.size() < numbers.size())
        v.push_back(0);
        
    // 순열
    // 1개 2개 ... v.size() 개 -> 순열
    for(int i=1; i<=v.size(); i++) {
        DFS(0, i);
    }
    
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    
    int ret = 0;
    for(int i=0; i<answer.size(); i++)
        if(prime(answer[i]) == true)
            ret++;
    
    return ret;
}

 

접근 방식

1.  string 인 numbers 를 int 로 변환

2. 숫자한자리씩 쪼개서 벡터 v 에 인서트

3. 앞에 0 이 붙는 경우를 포함하기 위해서 numbers 의 길이와 v 의 길이를 비교하여 0 을 push 해줌

4. 1개~v.size() 까지 각 갯수를 뽑아 만들 수 있는 순열을 구한다 (DFS)

5. 각 경우의 수를 answer 에 저장한 후

6. answer 를 중복제거한다.

7. 남은 answer 들의 원소를 소수 판별한다. (틀렸던 부분, 2를 소수로 인식해주지 않음)

 

다른 사람 코드 참고

next_permutaion() 사용 > do_while (do 내부의 구문을 일단 실행 후 while 조건을 판별)

next_permutaion() 사용 시 유의해야 할점

1. sort 를 미리 해주어야한다.

2. 구문 내부에 자료구조 수정이 일어나서는 안된다.

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


// 소수 판별 함수
bool prime(int no) {
	if(no <= 1)
		return false;
	if(no == 2)
		return true;

	for(int i=2; i<=sqrt(no); i++)
		if(no % i == 0)
			return false;

	return true;
}


int solution(string numbers) {

	int ret = 0;

	vector <int> answer;

	// 순열 구하고
    // next_permutaion 사용하려면 sort 를 우선 해주어야함
    sort(numbers.begin(), numbers.end());
	do {

		for(int i=1; i<=numbers.size(); i++) {
			int sub = stoi(numbers.substr(0, i));
			// 모든 경우 집어넣고
			answer.push_back(sub);

		}

	}while(next_permutaion(numbers.begin(), numbers.end()));

	// 증복제거
	sort(answer.begin(). answer.end());
	answer.erase(unique(answer.begin(), answer.end()), answer.end());
	// prime 판별
	for(auto n: answer)
		if(prime(n))
			ret++;

	return ret;
}