[프로그래머스/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은 같은 숫자로 취급합니다.

---

해당 문제는 string 으로 주어지는 문자열의 각 숫자들을 모두 조합하여 소수의 개수를 찾는 문제이다.

 

이때, 각 숫자들을 모두 조합할 때 순열을 이용하면 좋은데, 이러한 순열을 구현해주는 함수가 c++에 존재하고 있었다..!

💡 next_permutation (begin(), end())

위 함수를 사용하면 현재 나와있는 수열에서 인자로 넘어가는 범위에 해당하는 다음 순열을 구하고 true를 반환해준다.

다음 순열이 없다면 false를 반환한다.

 

반대로 다음 순열이 아닌, 이전 순열을 구하는 prev_permutation 함수도 존재한다!

 

이때 꼭 주의해야 하는 사항은 next_permutation 함수를 사용하기 전 배열을 꼭 정렬해야 한다는 점이다.

 

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

using namespace std;

bool IsPrime(int n)
{
	if (n <= 1) return false;

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

int solution(string numbers) {
	set<int> nums;

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

	do
	{
		string temp = "";
		for (char num : numbers)
		{
			temp += num;
			if(IsPrime(stoi(temp)))
				nums.insert(stoi(temp));
		}
	} while (next_permutation(numbers.begin(), numbers.end()));

	return nums.size();
}

 

나는 이러한 순열 함수를 이용해서 do~while문을 검사하였고, 그 결과, string형의 요소들(한 자릿수 숫자들)이 순서대로 서로다른 순열을 만들어내었다.

 

먼저, 완전탐색 문제인 만큼 숫자를 조합해서 나올 수 있는 모든 경우를 구했다.

"123" 이라는 string이 있다면, 

순열을 돌렸을 때 123, 132, 213, 231, 312, 321 까지 총 여섯가지 순열이 나온다.

 

각 순열이 도출됐을 때, "123"을 예로 들면, 

1, 12, 123 이 각각 소수인지를 확인하는 함수 IsPrime을 거친 뒤, 소수라면 set 배열에 추가해주었다.

 

마지막으로 소수의 개수는 set 배열의 크기를 반환하며 마무리했다.

 

소수를 찾는 방법에는 다양한 방법이 있지만, 나는 약수를 구할때와 마찬가지로, 제곱근을 이용한 방식으로 for문의 반복횟수를 줄였다.

 

그러나 소수 찾기에는 유명한 에라토스테네스의 체 알고리즘이 있기때문에 알고리즘에 대한 내용은 다른 게시글에 따로 정리하며 공부하였다.

---

참조

https://twpower.github.io/82-next_permutation-and-prev_permutation

[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기