[소수 찾기] - 완전탐색 ★★☆☆ / 복습 ○

[ 문제 ] : https://programmers.co.kr/learn/courses/30/lessons/42840

코딩테스트 연습 - 모의고사

---

[ 문제 접근 ]

 

우선 문제의 풀이 과정은,

순열을 구하고 구한 순열을 중복이 없는 set에 집어 넣고, set에서 하나씩 꺼내 소수를 판별해서 갯수를 cnt 해준다.

 

아리토스테네스의 체와 permutation(순열)을 따로 함수로 만들어서 사용했으며,

std::next_permutation은 사용하지 않고 공부한 순열을 직접 구현해 보았다.

 

다음 복습때는 std::next_permutation 사용해서 풀어봐야겠다.

---

[ 최종 코드 ]

 

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

using namespace std;
// 순열, 소수 구하기, set

std::set<int> ss;
vector<char> vec(8);
bool visited[8];

void permutation(int k, int r, int n, string numbers) {
	if (k == r) {
		string str = "";
		for (int i = 0; i < r; i++) {
			str += vec[i];
		}
		ss.insert(stoi(str));
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			vec[k] = numbers[i];
			visited[i] = true;
			permutation(k + 1, r, n, numbers);
			visited[i] = false;
		}
	}
}
bool is_prime(int num) {
	if (num < 2) return false;
	for (int i = 2; i <= std::sqrt(num); i++) {
		if (num%i == 0)return false;
	}
	return true;
}

int solution(string numbers) {
	int answer = 0;
	int size = numbers.length();

	// nP1, nP2 ... nPsize 의 모든 순열을 구해준다.
	for (int i = 1; i <= size; i++) {
		permutation(0, i, size, numbers);
		std::fill_n(vec.begin(), 8, NULL); // for 루프 돌때마다 전역 변수는 초기화
		std::fill_n(visited, 8, false);
	}

	for (auto& elem : ss) {
		if (is_prime(elem)) answer++;
	}

	return answer;
}

 

---

[ Key Point ]

 

👉 순열을 구할 수 있는지, 소수를 판별할 수 있는지가 문제의 핵심이었다.

 

---

[ 다른 사람 풀이 ]

 

ref :: https://intaehwang.tistory.com/11