프로그래머스 소수찾기 C++

문제는 먼저 numbers 가지고 만들 수 있는 모든 숫자들을 만들고, 만든 다음에 소수인지 확인하면 된다.

 

numbers가지고 만들 수 있는 모든 숫자들을 어떻게 만들 수 있을까?

c++ <algorithm> 에 정의되어 있는 next_permutation 함수를 사용했다

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cmath>

using namespace std;
unordered_map<int, int> m;

bool isPrime(int x) {
    if (x == 0 || x == 1) {
        return false;
    }
    if (x == 2) {
        return true;
    }
    for (int i = 2; i <= sqrt(x);i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<char> v;

    for (int i = 0; i < numbers.size();i++) {
        v.push_back(numbers[i]);
    }

    sort(v.begin(), v.end());

    do {
        string temp = "";
        for (int i = 0;i < v.size();i++) {
            temp.push_back(v[i]);
            m[stoi(temp)]++;
        }
    } while (next_permutation(v.begin(), v.end()));

    for (auto it = m.begin(); it != m.end(); it++) {
        if (isPrime(it->first)) {
            answer++;
        }
    }

    cout << answer << endl;
    return answer;
}

int main(void) {
    string numbers = "002";
    solution(numbers);
    return 0;
}

코드를 이렇게 작성했습니다. 

 

그런데 계속해서 2, 10, 11 테스트케이스만 틀렸다.

permutation함수가 사전 순으로 가장 가까운 다음 상태로 배열하는 함수이라고 한다. 따라서 시작 지점이 오름차순으로 정렬되어 있어야 모든 경우의 수를 만들 수 있다. 이를 고려해서 코드를 다시작성해서 맞췄다.