Level 2 소수 찾기

Approach

순열을 모두 구한 뒤, 각 값이 소수인지 판별.

Issues

순열 구하는 알고리즘을 모른다!

내부 함수인 next_permutation도 주어진 문자열과 같은 크기의 순열을 반환 할 뿐, 다른 크기의 문자열을 반환하지는 않는다.

어떻게 크기가 다른 문자열의 조합을 구할지에 대해서 시간을 좀 많이 소비했다.

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4set<int> myset;
5
6// O(sqrt N)
7bool isPrime(int n) {
8    if(n < 2) return 0;
9    if(n <= 3) return 1;
10    
11    if(n%2==0 || n%3==0) return 0;
12    
13    for(int i=5; (i*i)<=n; i+=6)
14        if(n%i==0 || n%(i+2)==0) return 0;
15    
16    return 1;
17}
18
19// O(S * 2^S)
20void permutate(string str)
21{
22  int n = str.length();
23  unsigned opsize = pow(2, n);
24
25  for (int i = 1; i < opsize; i++) // O(2^S)
26  {
27    string subs = "";
28    for (int j = 0; j < n; j++) // O(S)
29      if (i & (1<<j))
30        subs.push_back(str[j]);
31
32    do
33    {
34      myset.insert(stoi(subs)); // O(S)
35    } while (next_permutation(subs.begin(), subs.end())); // O(S/2) => O(S)
36  }
37}
38
39int solution(string numbers) {
40    sort(numbers.begin(), numbers.end()); // O(N * log(N))
41    permutate(numbers); // O(N * 2^N)
42    int answer = 0;
43    
44    // O(M * sqrt(M)), M = number of items in the set
45    for(auto it=myset.begin(); it != myset.end(); ++it)
46        if(isPrime(*it)) 
47            ++answer;
48    
49    return answer;
50}

Time Complexity

• O(N * logN) + O(S * 2^S) + O(M * sqrt(M)), S = length of a string, M = number of items in the set
  • => O(N * 2^N)

Space Complexity

• O(S), S = number of items in the set