소수 찾기

문제 링크 => 코딩테스트 연습 - 소수 찾기 | 프로그래머스 (programmers.co.kr)

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

---

numbers 가 주어질 때, 임의로 숫자들을 연결시켜서 소수가 되도록 하는 모든 경우의 수를 구하는 문제이다.

 

이때 numbers의 길이는 7이므로 최대 9,999,999 까지 나올 수 있다. => 즉, 소수를 직접 구할 경우 어마무시한 시간 초과가 일어날 것이다.

 

따라서 소수를 미리 판단할 수 있도록 에라스토테네스의 체를 이용하여 미리 소수인 경우를 구하도록 한다.

 

int x[10000000];

x[0] = x[1] = true;
for (int i = 2; i < 3200; i++) {
	if (!x[i]) {
		for (int j = i + i; j < 10000000; j += i) {
			x[j] = true;
		}
	}
}

 

모든 세팅이 끝났다.

 

그렇다면 next_permutation 을 이용하여 모든 경우를 살펴보면서 문자열 길이 1, 2, ... , numbers.size() 를 이어주면서 해당 값이 소수인지 판단하고 맞을 경우 카운팅만 해주면 끝이다.

 

근데 문제가 있다. 

 

예를 들어서 numbers = "1753" 이 주어졌을 경우 next_permutation 을 한다면 어떠한 숫자들이 나오게 될지 살펴보도록 한다.

 

string s = "1753";
do {
	cout << s << endl;
} while (next_permutation(s.begin(), s.end()));

 

 

뭔가 찝찝하게 permutation 이 돌아가는것을 확인할 수 있다.

 

우리는 1357, 1375, ..., 1735 이 숫자들을 확인하지 못했다.

 

이러한 찝찝함을 해결하기 위해 sort를 이용하여 numbers 를 오름차순으로 두고 다시 확인해보도록 한다.

 

string s = "1753";
sort(s.begin(), s.end());
do {
	cout << s << endl;
} while (next_permutation(s.begin(), s.end()));

 

 

sorting 을 오름차순으로 정렬하고 permutation을 돌리면 모든 경우가 나온다.

 

이제 단순하게 permutation 한 문자열에 대하여 문자열 길이 1, 2, ... , numbers.size() 를 이어주면서 해당 값이 소수인지 판단하고 맞을 경우 카운팅만 해주면 끝이다.

 

풀이 Code

 

#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool x[10000000];
map<int, bool> M;

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

	x[0] = x[1] = true;
	for (int i = 2; i < 3200; i++) {
		if (!x[i]) {
			for (int j = i + i; j < 10000000; j += i) {
				x[j] = true;
			}
		}
	}

    sort(numbers.begin(), numbers.end());

	do {
		string tmp = "";
		for (int i = 0; i < numbers.size(); i++) {
			tmp += numbers[i];
			int num = stoi(&tmp[0]);
			if (!M[num]) {
				M[num] = true;
				if (!x[num]) answer++;
			}
		}
	} while (next_permutation(numbers.begin(), numbers.end()));

	return answer;
}