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

소수 찾기 (Level 2)

문제

전체 문제 보기

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

접근법

이 문제에서 요구하는 것은 최대 7개의 주어진 숫자들로 만들 수 있는 모든 경우의 수 중에서 소수의 개수를 구하라는 것이다. 이 문제에서 고민이 필요한 알고리즘은 소수를 판별하는 방법과, 7개의 숫자로 만들 수 있는 모든 조합의 숫자를 만들 방법이 필요하다. 먼저 소수를 판별하는 방법을 살펴보자.

 

임의의 숫자 n이 소수인지 아닌지 판별하는 가장 쉬운 접근법은 직접 나눠보는 방법이다. 이문제에서 다루는 수의 크기는 7자리이기 때문에 최대 크기는 \(9,999,999\) 까지 나올 수 있다. 하지만 임의의 수 \(n\)이 소수인지 아닌지 파악하기 위해서는 \(2\)부터 \(n-1\)이 아닌 \(2\)부터 \(\sqrt{n}\) 까지만 나눠 보면 된다. 20이라는 숫자를 생각해보자. 20이 가진 모든 소인수를 구하려고 한다면 \(\sqrt{20}\)(약 4.47) 이하의 정수인 4까지만 나눠보면 된다. 왜냐하면 20에 1을 나누면 20이 나오고, 2를 나누면 10이 나오고 4를 나누면 5가 나오기 때문이다. 즉 \(\sqrt{n}\)이 정수인(7 * 7 = 49) 경우가 아니라면 \(\sqrt{n}\)보다 작은 소인수는 반드시 \(\sqrt{n}\) 보다 더 큰 짝을 가진다. 이 때문에 그 수가 소수인지 아닌지 파악하기 위해서는 \(\sqrt{n}\)까지만 살펴보면 된다. \(\sqrt{n}\)이하에서 나눠지는 값이 없다면, \(\sqrt{n}\) 보다 더 큰 수에서도 나눠지는 값이 존재할 수 없기 때문이다.

 

그다음으로 살펴볼 부분은 7개의 숫자를 조합하는 방법이다. C++에서는 std::next_permutation 함수를 활용하면 쉽게 구할 수 있다.
먼저 "1234567" 이라는 수 에서 한 자리부터 일곱 자릿수를 순서 그대로 뽑아보자.

1234567 → "1234567" / "234567" / "34567" / "4567" / "567" / "67" / "7"

next_permutation 함수는 하나의 문자열을 사전순 기준으로 그다음 높은 수로 만드는 함수이다. 1234567에서 그다음 높은 수로 만들면 1234576이 된다. 그러면 이 수에서도 한 자릿수부터 일곱 자릿수 를 순서 그대로 뽑아보자.

1234567 → 1234576
1234576 → "1234576" / "234576" / "34576" / "4576" / "576" / "76" / "6"

next_permutation 함수는 문자열을 사전순 기준으로 그다음 높은 수로 만들 면 true를 반환한다. 만약 더 높은 수가 더 이상 존재하지 않는다면 false를 반환한다. 즉, 1234567을 시작으로 가장 큰 7654321을 만든 다음에 next_permutation을 호출하면 false가 반환된다. 이를 활용하면 1234567로 만들 수 있는 모든 경우의 수를 만들어 낼 수 있다. next_permutation 함수가 false가 될 때까지 위의 작업을 반복해 주면 1234567로 만들 수 있는 모든 경우의 수를 만들어낼 수 있다. 이때 주의할 점은 numbers가 반드시 정렬되어 있어야 한다. 만약 입력된 numbers가 "132"라면 "132"→ "213" → "231" → "312" → "321" → (flase 반환) 이기 때문에. "123"이라는 경우의 수는 고려될 수 없다.

 

마지막으로 고민해봐야할 부분은 소수 계산을 위해서 만들어진 수의 중복 제거이다. 예를 들면 "117"라는 입력이 들어온다면, 위와 같은 알고리즘에서는 "1"이 나 "17"이 중복으로 입력될 수 있다. 더욱이 "17"은 소수이기 때문에 소수가 중복으로 입력되면 원하는 값을 얻을 수 없다. 중복 제거를 위해서 앞서 뽑은 수들은 vector에 저장하고 정렬 후 unique 함수와 erase 함수를 사용할 수는 있다. 하지만 애초에 뽑은 수를 vector가 아니라 set 저장하면 조금 더 효율적으로 중복을 제거할 수 있다. set은 애초에 중복 값을 허용하지 않기 때문에 중복된 요소는 알아서 삽입이 되지 않기 때문이다.

구현

#include <string>
#include <cmath> //sqrt()
#include <set>
#include <algorithm>

using namespace std;
// 소수 판별 식
bool IsPrime(int num)
{
    if (num < 2)
        return false;

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

int solution(string numbers) {
    int answer = 0;

    set<int> combinableNumbers;
    // next_permutation() 함수로 모든 경우의수를 만들기 위해서는 반드시 정렬
    sort(numbers.begin(), numbers.end());
    do
    {
        // 해당 수에서 한 자리 수 부터 numbers.size() 자리 수 까지 추출하여 set에 저장
        for(int i = 1; i <= numbers.size(); i++)
        {
            int number;
            number = stoi(numbers.substr(0,i));
            combinableNumbers.emplace(number);
        }
    }
    // 모든 경우의 수를 만들어냈다면 false 반환
    while(next_permutation(numbers.begin(), numbers.end()));

    // set에 저장된 모든 조합가능 수에 대해 소수 판별
    for(int number : combinableNumbers)
    {
        if(IsPrime(number) == true)
            answer++;
    }
    return answer;
}