[프로그래머스][C++][완전탐색] 소수 찾기

문제

문제 링크 - 소수 찾기

풀이

알고리즘

• 입력값(numbers) 오름차순 정렬
• next_permutation 메소드를 사용하여 가능한 모든 조합을 구함
• 조합을 구하는 동시에 중복값 제거를 위해 set에 넣어줌
• 에라토스테네스의 체를 이용해 소수를 구해줌

코드

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

int solution(string numbers)
{
    int answer = 0;
    set<int> my_set;

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

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

    int max_num = *my_set.rbegin();
    vector<bool> isPrime(max_num, true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (int i = 2; i * i <= max_num; i++)
    {
        if (isPrime[i])
            for (int j = i * i; j <= max_num; j += i)
                isPrime[j] = false;
    }

    for (auto iter = my_set.begin(); iter != my_set.end(); iter++)
    {
        if (isPrime[*iter])
            answer++;
    }

    return answer;
}

주석 코드

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

int solution(string numbers)
{
    int answer = 0;
    set<int> my_set;  //중복값을 제거하기 위해 set 사용

    //모든 순열 조합을 구하기 위해 오름차순 정렬
    sort(numbers.begin(), numbers.end());

    cout << "조합의 경우의 수" << endl;
    do
    {
        string temp = "";
        for (int i = 0; i < numbers.size(); i++)
        {
            temp += numbers[i];
            my_set.insert(stoi(temp));
            cout << temp << ", ";
        }
        cout << endl;

    } while (next_permutation(numbers.begin(), numbers.end()));
    cout << endl;

    cout << "만들어진 조합 중 중복값 제거" << endl;
    for (auto iter = my_set.begin(); iter != my_set.end(); iter++)
    {
        cout << *iter << ", ";
    }
    cout << endl
         << endl;

    //*my_set.rbegin() ==> my_set의 가장 마지막 값(가장 큰 값)
    int max_num = *my_set.rbegin();
    //소수 판별 벡터를 가장 큰 값의 크기만큼 초기화
    vector<bool> isPrime(max_num, true);
    //숫자 0,1은 소수가 아니므로 false
    isPrime[0] = false;
    isPrime[1] = false;

    cout << "에라토스테네스의 체" << endl;
    for (int i = 2; i * i <= max_num; i++)
    {
        if (isPrime[i])
            for (int j = i * i; j <= max_num; j += i)
                isPrime[j] = false;
    }

    for (int i = 0; i < isPrime.size(); i++)
    {
        if (isPrime[i])
            cout << i << ", ";
    }
    cout << endl
         << endl;

    //iter가 my_set을 순회하면서 isPrime[*iter]가 소수라면 answer++
    for (auto iter = my_set.begin(); iter != my_set.end(); iter++)
    {
        if (isPrime[*iter])
            answer++;
    }

    return answer;
}

int main()
{
    string numbers1 = "17";  //1,7,17,71
    string numbers2 = "101"; //0,1,10,11,101,110

    int answer = solution(numbers2);
    cout << "answer: " << answer << endl;
}

주석 코드 출력 결과

조합의 경우의 수
0, 01, 011,
1, 10, 101,
1, 11, 110,

만들어진 조합 중 중복값 제거
0, 1, 10, 11, 101, 110,

에라토스테네스의 체
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
101, 103, 107, 109,

answer: 2

여담

이번 문제는 이해는 쉽지만 구현 난이도가 조금 있는 편이었다.
'문자열로 이루어진 숫자 input -> 순열 조합 구하기 -> 소수 판별하기'의 과정으로 이루어지는데 순열의 개념을 알고는 있었지만 next_permutation 메소드의 사용법과 개념을 잘 알지 못해서 애를 먹었다.

next_permutation가 순열을 구할 때는 일단 오름차순으로 정렬한 값을 주어야 한다는 것을 모르고 사용했는데, 오름차순 정렬을 하지 않으니 오름차순 -> 내림차순으로 바꿔가며 순열 결과를 주는 next_permutation이 중간 순열의 값부터 주는 것이었다.

하지만 next_permutation의 순열을 구하는 방식을 통해 모든 조합을 set에 insert 해줄 수 있었는데, 이 덕분에 또 다른 반복문을 통한 중복값 제거 과정을 다시 거치지 않고 깔끔하게 처리해줄 수 있었다. 매우 만족스러운 부분.
얼마 전 hash 문제들을 풀면서 set 또한 공부한 덕분이 아닌가 싶다.

마지막으로 에라토스테네스의 체는 예전에 백준 문제를 통해 구현한 기억이 있어서 별로 어려운 부분은 아니었다. 개인적으로 에라토스테네스의 체는 직관적이면서도 효율적이라 참 대단하다 싶은 느낌은 있다.