문제
문제의 시간복잡도
현재 n의 값은 7입니다. 이런 경우의 문제에서는 시간복잡도를 따지지 않고 풀어도 된다 생각을 했습니다.
문제의 접근법
문제에서 구해야 하는 것은 크게 두가지 입니다.
첫번째 : 주어진 문자열을 통해서 만들 수 있는 모든 경우의수
두번째 : 이렇게 구한 조합의 수가 소수인지 아닌지의 판가름
모든 경우의수 구하기
이를 구하기 위하여 사용한 것은 DFS입니다.
그래프의 깊이 탐색을 통하여 추가 및 다음 요소를 추가 해주는 방식으로 진행을 했습니다.
예시를 한번 들어 보겠습니다.
numbers.size() 값이 4일때에 그래프의 모습입니다.
여기에 예시로 numbers = "1234" 일 때 1을 먼저 추가 했을 때를 기준으로 그래프의 노드 값을 채운 결과를 보여드리겠습니다.
먼저 1은 추가가 되었습니다. 이런 1은 추가적으로 2,3,4를 추가 할 수 있을 것입니다. 그렇기 때문에 노드로 2,3,4를 가집니다.
그리고 Level=2 에서 노드 2,3,4는 또 각각이 위의 사진의 Level=3의 노드들을 뒤에 추가를 할 수 있을 것입니다.
그리고 마지막으로 Level=3의 노드들은 Level=4의 노드들을 가질 수 있을 것입니다,
여기서 답은 다 나왔습니다.
이제 이 노드를 Level1부터 Level4까지 이동을하면서 각각의 값을 추가해주면 되겠습니다.
한가지 예시만을 들어보겠습니다.
빨간 화살표는 탐색을 하는 과정입니다.
위의 그래프에서 먼저 1을 탐색을 할 것입니다. 그렇다면 이 1을 배열에 저장을 합니다.
현재 그러면 배열은 [1] 의 상태일 것입니다.
그리고 다음은 2를 탐색을 할 것입니다. 이 때, 1에 2를 붙혀줍니다.
그러면 그 값은 12가 되고 이것을 배열에 추가를 합니다.
그러면 배열은 [1,12]가 될 것입니다.
그리고 그다음은 3을 추가해서 [1,12,123]
그리고 그다음은 4를 추가해서 [1,12,123,1234] 이런 결과를 얻을 수 있게 됩니다.
위와 같은 방법으로 탐색하지 않은 노드들을 모두 탐색을 하면 결과적으로 모든 원소의 값을 얻을 수 있습니다.
소수
소수를 구하는 방법은 쉽습니다.
일단 소수란 1과 자기자신을 제외한 그 어떤 수도 약수로서 같지 않는 수를 이야기 합니다.
그래서 이 소수를 구히기 위해서는 2부터 자기자신 전 까지의 수로 모듈 연산을 하여 그값이 0이 아닌지를 판단하면 됩니다.
근데 이렇게하면 n번을 돌아야 그 결과를 알 수 있으므로 이를 줄이기 위하여 n에 루트를 씌워서 다시 같은 연산을 해줄 때, 같은 연산 결과를 얻을 수 있습니다.
왜냐하면 수는 X * Y로 값을 구 할 수 있습니다. 그래서 어떤 수를 구할 때의 약수는 짝이 지어지고 그 짝은 결국 루트를 씌웠을 때 왼쪽 값들만을 비교 할 수 있습니다.
풀이
#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <cmath>
using namespace std;
vector<int> v;
set<int> s;
void dfs(int x, int y,bool check[])
{
for(int i=0;i<v.size();i++)
{
if(check[i]==false)
break;
else
{
if(v.size()-1 == i)
return;
}
}
bool f_check[7];
copy(check,check + 7, f_check);
int a = (x*10)+v[y];
s.insert(a);
f_check[y] = true;
for(int i=0;i<v.size();i++)
{
if(f_check[i] == false)
dfs(a, i, f_check);
}
}
int solution(string numbers) {
int answer = 0;
for(int i=0;i<numbers.size();i++)
v.push_back(numbers[i]-48);
bool check[7] = {false, };
for(int i=0;i<numbers.size();i++)
dfs(0,i,check);
for(auto i=s.begin() ;i != s.end();i++)
{
bool flag = true;
cout << (*i) << " ";
for(int j=2;j<=sqrt((*i));j++)
{
if((*i)%j == 0)
{
flag=false;
break;
}
}
if(flag==true && *i!=0 && *i!=1) answer++;
}
return answer;
}
1) numbers의 각 char 요소들을 int형으로 변환하여 vector에 저장을 하였다.
2) 그리고 check라는 배열을 두어 false로 초기화를 하였다.
3) numbers 요소들을 저장했던 vector의 각 요소들에 대하여 for문을 돌면서 dfs를 실행하였다.
4) int형을 저장하는 set 컨테이너를 하나 생성하였다.
( 중복된 값은 저장되지 않게 하기 위해서 )
5) dfs는 먼저 check 배열을 확인한다. check 배열이 모두 true라면 모든 찢겨진 종이를 다 사용 했다는 것이다.
6) 그리고 dfs의 인수로 받은 numbers의 한 요소를 뒤에 이어 붙혀주고 set에 값을 추가한다.
7) 다시 check값이 false인 것에 한하여 dfs를 재귀적으로 해준다.
( 그래프로 따지면 자식노드를 추가해주는 것이다. )
8) 이렇게 모든 경우의 수가 들어가 있는 set의 모든 요소를 확인하여 소수인지를 판가름 한다.
기타
"copy"
copy( 복사할배열의주소, 배열의주소+어디전까지복사하는가, 결과를넣을배열의주소);
c++은 배열을 인수로 넣을 때 배열의 주소가 들어가므로, 인수의 값을 복사해서 사용 하고 싶은 경우 위와같은 copy 함수를 사용 할 수 있다.
