[프로그래머스] 소수찾기
April 17, 2021
https://programmers.co.kr/learn/courses/30/lessons/42839
문제
문제
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
풀이
- 먼저 에라토스테네스의 채로 소수 리스트를 만들어둔다. 문제에서 종이조각의 개수가 최대 7개로 주어졌기 때문에 나는 그냥 9999999 까지의 소수를 모두 구해줬다.
- 백트래킹을 통해 문자열을 조합한다. 조합할 때 개수와 상관없이 모든 조합을 만들어낸다.
- stoi 함수를 사용해서 정수로 변환한 뒤에, 소수인지 판별하고 이미 사용한 적이 있는 숫자인지도 판별해서 갯수를 세어준다.
코드
{% raw %}
#include <string>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
#define MAX 9999999
bool visited[MAX];
bool isUsed[MAX] = { 0, };
string comb;
int count = 0;
void dfs(int size, vector<bool> primes, string numbers) {
if (!comb.empty() && comb.size() <= size) {
int num = stoi(comb);
if (!isUsed[num] && primes[num]) {
cout << comb << endl;
isUsed[num] = true;
count++;
}
if (comb.size() == size) return;
}
for (int i = 0; i < numbers.size(); i++) {
if (!visited[i]) {
visited[i] = true;
comb.push_back(numbers[i]);
dfs(size, primes, numbers);
comb.pop_back();
visited[i] = false;
}
}
}
int solution(string numbers) {
int answer = 0;
vector<bool> primes(MAX, true);
primes[0] = false;
primes[1] = false;
for (int i = 2; i <= sqrt(MAX); i++) {
for (int j = i + i; j <= MAX; j += i) {
primes[j] = false;
}
}
dfs(numbers.size(), primes, numbers);
return count;
}
{% endraw %}
