[프로그래머스 lv2] 소수 찾기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

문자열에 주어진 숫자들로 만들 수 있는 모든 순열과 순열의 부분집합에 대하여 소수인 것의 개수를 리턴하는 문제이다.

먼저, 문자들로 만들 수 있는 모든 수들을 탐색하기 위해 백트래킹(재귀)를 사용한다.

 

배열에 저장된 인덱스를 숫자로 바꾼 뒤, 해당 수가 소수인지 확인한다.

소수인지 확인할 떄는, isPrime() 함수를 별도로 만들어 일일이 호출하기 보다, 에라토스테네스의 체를 활용하여 한번에 소수를 확인하는 배열을 만들어놓고 O(1)에 처리한다.

아래의 코드에서는 check 배열을 false로 초기화해 놓고, 소수가 아닐 경우와 이미 카운트 했을 경우에 check[i] 값을 true로 변환하였다.

 

함꼐 참고하면 좋을 포스트

바킹독님의 실전알고리즘-백트래킹

소수 판별 알고리즘과 에라토스테네스의 체

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int K, cnt;
int arr[10];
bool isused[10];
bool check[10000000];

void eratos() {
    
    check[0] = true; 
    check[1] = true;
    for (int i=2; i*i<10000000; i++) {
        if (check[i]) continue;
        for (int j=i*i; j<10000000; j+=i)
            check[j] = true;
    }
}

int getNum(int k, const string& numbers) {
    
    int n = 0;
    int p = 1;
    for (int i=k-1; i>=0; i--) {
        n += (numbers[arr[i]]-'0')*p;
        p *= 10;
    } 
    return n;
}

void func(int k, const string& numbers) {
    
    if (k > K) return ;
    int n = getNum(k, numbers);
    if (!check[n]) {
        cnt++;
        check[n] = true;
    }
    
    for (int i=0; i<K; i++) {
        if (isused[i]) continue;
        isused[i] = true;
        arr[k] = i;
        func(k+1, numbers);
        isused[i] = false;
    }
}

int solution(string numbers) {
    
    eratos();
    K = numbers.size();
    func(0, numbers);
    return cnt;
}