[프로그래머스] 레벨 2 - 소수 찾기

완전 탐색 문제다.

접근법을 dfs로 백트래킹하여 찾아보려 했으나 '순차적인' 문자열만 만들 수 있어 풀이가 어려웠다.

길이가 1부터 전체 사용하는 문자열을 만들 수는 있지만, numbers로 "17"이 주어졌을 때

"1", "7", "17"은 만들 수 있지만 "71"은 만들 수 없다.

 

그래서 다른 방법을 생각해봤다.

 

"주어진 숫자를 내림차순하고 각 숫자를 이루는 숫자가 몇 번 등장하는지 배열을 써서 2부터 주어진 숫자까지 루프를 돌면서 그 숫자에 등장하는 숫자들이 배열의 요소 이하로 등장하는지 검사하고, 이것이 소수이면 answer++하자!"

 

즉, 내림차순하면 최대 범위를 구하게 되는 것이고, 2이상의 값부터 검사를 해서 유효한 숫자이면 소수검사를 하는 것이 알고리즘이다. 만약 1이하의 값이 numbers로 주어지면 그냥 0을 반환하도록 했다.

 

아래는 소스코드.

 

#include <string>
#include <vector>
#include <functional>
#include <algorithm>
#include <sstream>
using namespace std;
int cnt[10], tmp[10];
 
int solution(string numbers) {
    int answer = 0;
    for(int i=0; i<10; i++) {
        cnt[i] = 0;
        tmp[i] = 0;
    }
    sort(numbers.begin(), numbers.end(), greater<char>());
    int maxval;
    stringstream s_str(numbers);
    s_str >> maxval;
    if(maxval <= 1) return 0;
    for(int i=0; i<numbers.length(); i++){
        cnt[numbers[i]-'0']++;
        tmp[numbers[i]-'0']++;
    }
    for(int i=2; i<=maxval; i++){
        bool cannotmake=false;
        ostringstream ostr;
        ostr << i;
        string curstr = ostr.str();
        for(int j=0; j<curstr.length(); j++){
            cnt[curstr[j]-'0']--;
            if(cnt[curstr[j]-'0'] < 0){
                cannotmake = true;
                break;
            }
        }
        if(!cannotmake){
            // i는 만들 수 있는 숫자임. i가 소수인지 검사.
            bool isPrime = true;
            for(int j=2; j<i-1; j++){
                if(i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) answer++;
        }
        else{
            // 만들 수 없는 숫자.
        }
        for(int j=0; j<10; j++)
            cnt[j] = tmp[j];
    }
    return answer;
}