[프로그래머스] 코딩테스트 연습 > 완전탐색 > 소수 찾기 (C++)

//C++
#include <bits/stdc++.h>

using namespace std;

bool isPrime(int check)
{
    if (check < 2) return false;

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

int solution(string numbers) {

    string tmp = "";
    set<int> s;

    vector<int> s_numbers;
    for (int i = 0; i < numbers.length(); i++)
    {
        s_numbers.push_back(numbers[i]);
    }
    sort(s_numbers.begin(), s_numbers.end()); //next_permutation 하기 전에 sorting 하지 않으면 원하는 결과 만들 수 없다..

    do //카드들로 만들 수 있는 모든 자릿수의 수들을 만드는 데에 고생을 함..
    {
        tmp = "";
        for (int i = 0; i < s_numbers.size(); i++)
        {
            tmp += s_numbers[i];
            s.insert(stoi(tmp));
        }

    } while (next_permutation(s_numbers.begin(), s_numbers.end()));

    //소수 개수 체크
    int prime_ans = 0;
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        if (isPrime(*it)) 
        {
            prime_ans += 1; 
        }
    }

    return prime_ans;
}

- 종이 조각들을 이어서 만들 수 있는 모든 숫자들을 만들고, 그 숫자들 중 소수의 개수를 세는 문제이다.

 

- 여러 조각들로 만들 수 있는 모든 경우의 숫자들을 일단 set에다가 담아야 한다. set을 쓴 이유는 같은 숫자를 두 번 만드는 경우 중복을 제거하기 위함이다. (set이 아니라 vector를 이용하고, unique와 erase를 통해서 중복을 제거하는 방법도 존재한다.)

 

- 버블 소트를 이용하여, 모든 경우의 숫자들을 만들 수 있을 거라 생각했지만, 이중 for 문을 이용한 버블 소트는 오로지 두 자릿수의 숫자만 만들 수 있었다.

 

-  do { } while 문 내의 코드와 next_permutation의 힘으로 모든 경우의 숫자들(조각들로 만들 수 있는 모든 자릿수의 숫자들)을 만들 수 있었다. 

 

- 물론 next_permutation을 사용하기 전에, sorting 을 해야하므로 sorting 을 먼저 해주었다.

 

- set 내에 있는 모든 숫자들을 하나씩 꺼내어서(완전 탐색, Brute Force), 이 숫자가 소수인지를 판단하는 isPrime 함수를 사용했다.

 

- isPrime 함수 내에서 2 ~ check-1로 범위 설정을 해도 이 문제에서는 정답이지만, 그것보다는 2 ~ sqrt(check)로 범위 설정을 하는 것이 더 빠르다.