소수찾기 Programmers 프로그래머스 C++

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

구현

소수를 찾는 방법은 여러가지가 있다.

1. N^2 방법의 자신의 수보다 작은 수로 나누는 방법의 소수찾기
2. N^2 방법의 자신의 수를 제곱근을 한 값보다 작은 수로 나누는 방법의 소수찾기
3. 에라토스 테네스의 체

정도가 있다. 나는 2번의 방법으로 자신의 제곱근까지를 나눴을 때 떨어지는 값을 찾는 방법으로 구하였다.

---

<이후 해당 문제는 단순하게 소수를 찾기만 해서는 안되기 때문에 새로운 방식으로 접근이 필요하다.>

for (int i = 0; i < numbers.size(); i++) {
	number.push_back(numbers[i] - '0');
}
sort(number.begin(), number.end());

• 우선 numbers로 들어오는 수를 모두 1개씩 나눠서 number 벡터에 저장해주고 sorting 해준다.

do {
	int temp = 0;
	for (int i = 0; i < number.size(); i++)
	{
		temp = temp * 10 + number[i];
		num_vec.push_back(temp);
	}
} while (next_permutation(number.begin(), number.end()));

• 이후 number 벡터를 순열의 순서대로 돌리면서 num_vec 벡터에 모두 저장해준다.
• next_permutation() 함수는 vector에 1,2,3,4 가 들어있다면
  1 2 3 4 / 1 2 4 3 / 1 3 2 4 / ..... / 4 2 3 1 / 4 3 1 2 / 4 3 2 1 까지 모두 돌면서 탐색해준다.

sort(num_vec.begin(), num_vec.end());
num_vec.erase(unique(num_vec.begin(), num_vec.end()), num_vec.end());

for (int i = 0; i < num_vec.size(); i++) {
	answer += prime(num_vec[i]);
}
return answer;

• 이후 num_vec를 sorting 해주고 중복 되는 값을 모두 제거해준다.
• 이 문제의 경우 예를 들어 112 로 들어올 경우 순열로 돌리게 되면 112는 2번이 들어오게 되고 모두 저장되기 때문에 꼭 필요한 과정이다.
• erase(a,b) 함수는 a~b까지의 모든 원소를 삭제해주는 함수이다.
• erase의 경우 unique 함수와 함께 사용하게 되면 중복된 모든 수를 제거해주는 함수가 되는데 위의 함수 처럼
  erase(unique(a,b),b)를 하게 되면 a~b까지 있는 원소 중 반복되는 모든 원소를 뒤로 보내주고 그 지점 부터 마지막 까지의 원소를 지울 수 있게 된다.
• 이후 answer의 값에 num_vec에 들어가 있는 모든 원소들을 소수 판별을 해주며 그 값을 카운팅 해서 더해준다.

전체 코드는 아래에서 볼 수 있다.

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

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

int solution(string numbers) {
	vector<int> number;
	vector<int> num_vec;
	int answer = 0;

	for (int i = 0; i < numbers.size(); i++) {
		number.push_back(numbers[i] - '0');
	}
	sort(number.begin(), number.end());

	do {
		int temp = 0;
		for (int i = 0; i < number.size(); i++)
		{
			temp = temp * 10 + number[i];
			num_vec.push_back(temp);
		}
	} while (next_permutation(number.begin(), number.end()));
	
	sort(num_vec.begin(), num_vec.end());
	num_vec.erase(unique(num_vec.begin(), num_vec.end()), num_vec.end());

	for (int i = 0; i < num_vec.size(); i++) {
		answer += prime(num_vec[i]);
	}
	return answer;
}

확실히 프로그래머스 문제들은 level2 이상 부터가 진짜 문제다.

level1의 경우 백준의 실버~골드 정도 수준의 문제 밖에 되지 않아 누구나 쉽게 풀어낼 수 있지만 level2 이상의 문제는 높게는 골드1 이상의 문제도 나오기 때문에 대부분의 코딩 테스트가 level3 이상의 문제들이 많이 나온다는 것을 감안할 때 더욱 노력해야할 필요가 있다.