[Programmers] 소수 찾기

문제

코드

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

set<int> allComb;

void permutation(string str, int depth, int n, int r)
{
    if (depth == r)
    {
        string temp = "";
        for(int i = 0; i < r; i++)
        {
            temp += str[i]; 
        }
        
        allComb.insert(stoi(temp));
        
        return;
    }
    
    for(int i = depth; i < n; i++)
    {
        iter_swap(str.begin() + depth, str.begin() + i);
        permutation(str, depth + 1, n, r);
        iter_swap(str.begin() + depth, str.begin() + i);
    }
}

int solution(string numbers) {
    int answer = 0;
    int max = 10;
    for(int i=0; i<numbers.size(); i++){
        max*=10;
    }
    
    // 소수 체크
    vector<bool> check(max, true);
    for(int i=2; i<max; i++){
        if(check[i]==true){
            for(int j=2; i*j<max; j++) check[i*j] = false;
        }
    }
    check[0] = false; check[1] = false;
    for(int i=1; i<=numbers.size(); i++){
        permutation(numbers,0,numbers.size(),i);
    }
    
        
    for(auto & num : allComb){
         cout<<num<<" ";
         if(check[num]) answer++;
     }
    
   
    return answer;
}

풀이

• 완전탐색에서는 순열이 자주 등장하나보다. 저번에 피로도문제 풀 때는 cpp에서 제공하는 기능을 이용했는데, 이번에는 직접 구현해봤다. 다른 사람 풀이를 보니까 substr과 nextPermutation을 이용해서 조합을 구해내는 방법도 있었다.

• permutation함수의 경우 재귀를 이용해 순열을 구한다.
  기본적인 매커니즘은
  a, b, c, d 배열이 있을 때, a, b, c, d 각각이 맨 앞에 오는 경우로 나눠진다.
  예를 들면 a x x x, b x x x, c x x x, d x x x 이렇게 4경우다.
  뒤의 x x x도 비슷한 원리로 케이스가 나눠진다.
  따라서 매개변수로 depth와 r, 그리고 배열의 길이 n을 넘겨주고 depth부터 n까지 depth번째에 오는 문자를 교체해가면서 permutation함수를 재귀적으로 호출한다.

• 나는 미리 check배열에 소수를 체크해두고 set에 저장된 케이스들을 하나씩 소수인지 확인하는 방법을 사용하였다.

이번에도 순열 구현을 다른 코드들을 참고해서 했는데, 다음번에 순열 문제가 나오면 참고하지 않고 혼자서 짜봐야겠다.