알고리즘(C++) / 프로그래머스 level 2 : 소수 찾기

level 2 : 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839?language=cpp 

코딩테스트 연습 - 소수 찾기

 

코드

//프로그래머스 소수찾기
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

//소수 판별
bool prime(int num) {
    if (num < 2) 
        return false;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) 
            return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end()); // 오름차순 정렬
    map<int, int> m; //소수 저장
    //비트 바스킹으로 수 뽑아내기
    for (int i = 1; i < (1 << numbers.size()); i++) {
        vector<char> v; //뽑아낸 수 저장
        for (int j = 0; j < numbers.size(); j++) {
            if (i & (1 << j)) {
                v.push_back(numbers[j]);
            }
        }
        //조합
        do {
            string s = "";
            for (int k = 0; k < v.size(); k++) {
                s += v[k];
            }
            //cout << s << "\n";
            //소수 판별
            if (prime(stoi(s)))
                m[stoi(s)]++;
        } while (next_permutation(v.begin(), v.end()));
    }
    answer = m.size();
    return answer;
}

int main() {
    string numbers = "17";
    cout << solution(numbers) << "\n";
    return 0;
}

 

설명

• 조합을 구하는 next_premutation를 사용하기 위해서는 무조건 오름차순으로 정렬되어 있어야 한다. 따라서 numbers를 오름차순으로 정렬해준다.
• 비트 마스킹으로 수를 뽑아낸다. (예) numbers=17이라면 1, 7, 17 차례로 수를 뽑아낼 수 있다.
• 뽑아낸 수의 조합을 구하여 소수인지 판별한다.
• 소수이면 m에 저장한다. map에 저장하는 이유는 중복을 확인하기 위해서이다. 
• answer은 m의 size를 출력한다. 

 

고찰

걸린시간 : 20분

저번에 풀어본 후보키 문제나 조합을 푸는 문제를 풀어보고 이 문제를 풀었을 때 딱히 어렵지 않아서 쉽게 풀 수 있었다. 

다른 사람들의 풀이를 보고 비트 마스킹으로 수를 뽑아내지 않고 조합으로만으로 문제를 풀 수 있다는 것을 알 수 있었다. 하지만 numbers의 길이가 길어지면 중복되는 수가 늘어나기 때문에 시간이 더 늘어나게 된다는 것을 알 수 있었다. 비트 마스킹으로 풀기 어려울 때는 다음과 같은 방법으로도 풀 수 있다는 것을 알 수 있었다.

비트마스킹으로 수를 뽑아냈을 때

비트 마스킹으로 수를 뽑아내지 않았을 때

//프로그래머스 소수찾기
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

bool prime(int num) {
    if (num < 2) 
        return false;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) 
            return false;
    }
    return true;
}


int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end()); // 오름차순 정렬
    map<int, int> m;
    vector<char> vec;
    for (int i = 0; i < numbers.size(); i++) {
        vec.push_back(numbers[i]);
    }

    do {
        string s = "";
        for (int i = 0; i < vec.size(); i++) {
            s += vec[i];
            if (prime(stoi(s)))
                m[stoi(s)]++;
        }
    } while (next_permutation(vec.begin(), vec.end()));

    answer = m.size();
    return answer;
}

int main() {
    string numbers = "17";
    cout << solution(numbers) << "\n";
    return 0;
}

 

비트마스킹으로 수를 뽑아내지 않았을 때