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

Pixabay로부터 입수된 Gerd Altmann님의 이미지 입니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 이번 문제는 몇 가지의 숫자가 주어졌을 때, 이 숫자들을 조합하여 만든 숫자들 중 소수가 몇 개인지를 세는 문제이다. 이 문제의 해결 방법은 크게 두 단계로 나눌 수 있다. 우선은 숫자를 조합하는 방법이다. 만약 123이라는 숫자가 주어진다고 하자. 그렇다면 이 숫자들을 조합하여 만들 수 있는 숫자들은 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321이다. 즉, 만들 수 있는 숫자들은 길이가 1부터 주어진 숫자들의 개수이며 조합하는 순서가 중요하다. 이를 고려하여 숫자를 조합하는 코드는 대략 다음과 같다.

string 만든숫자 = "";

void 숫자만들기(int 길이)
{
    if (만든숫자.size() == 길이)
    {
    	cout << 만든숫자 << endl;
        return;
    }
    
    for (int i = 0; i < 주어진숫자.size(); ++i)
    {
        if (used[i] == false)
        {
            used[i] = true;
            만든숫자 += allNumbers[i];
            
            숫자만들기(길이);
            
            만든숫자.pop_back();
            used[i] = false;
        }
    }
}

 만약 만든 숫자의 길이가 만들어야 하는 숫자의 길이를 충족한다면, 특정 작업을 실행한다. 그렇지 않다면 처음부터 모든 숫자들을 하나씩 검사하여, 사용하지 않은 숫자라면 그 숫자를 만드는 숫자 뒤에 덧붙인다. 이런 과정을 통해 순서를 신경써서 모든 가능한 경우의 수를 만들 수 있다.

 그리고 문제를 해결하기 위해 신경써야 할 두 번째는, 소수를 검사하는 방법이다. 소수를 검사하는 방법에는 에라토스테네스의 체 등, 여러가지가 있다. 하지만 이번 문제를 해결하기 위해서 그냥 2부터 만든 숫자의 제곱근까지 하나씩 다 검사하는 방법을 이용할 것이다. 

for (int k = 2; k * k <= number; ++k)
{
	if (num % k == 0)
    {
    	cout << num << "은 소수가 아닙니다!" << endl;
        return;
	}
}

cout << num << "은 소수입니다!" << endl;

 위의 코드에서 소수인지 판별하기 위해 2부터 나눗셈을 시작하고 k * k <= number일 때까지 나눗셈을 진행한다. 우선, 나눗셈을 2부터 진행하는 이유는 소수의 정의때문인데, 소수는 1과 자기 자신으로만 나눠 떨어지는 수이기 때문이다. 그렇기에 2부터 나눗셈을 진행한다. 그리고 number의 제곱근(k * k == number인 점을 이용)까지 검사를 진행하는 이유는 다음과 같다. 예를 들어, 20이라는 숫자는 1, 2, 4, 5, 10, 20을 약수로 갖는다(1 * 20 == 2 * 10 == 4 * 5). 이 때, 20을 4로 나누었을 때 나머지가 0이라는 사실을 안다는 것은, 20을 5로 나누었을 때도 나머지가 0이라는 것을 안다는 뜻이다. 마찬가지로 20을 2로 나누었을 때 나머지가 0이라는 사실을 알면 20을 10으로 나누었을 때도 마찬가지라는 것을 안다. 즉, 나눗셈의 나머지 검사는 해당 숫자의 제곱근까지만(절반만) 검사하면 전체적인 결과를 알 수 있다. 그렇기에 반복문은 제곱근까지만 진행한다. 

 이를 고려해 작성한 답안은 다음과 같다.

#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAX 10000001

int answer = 0;
bool used[MAX];
bool checked[MAX];
string allNumbers;
string result;

void Check(int len)
{
    if (result.size() == len)
    {
        int num = stoi(result);
        
        if (checked[num] == true)
            return;
        checked[num] = true;
        
        // 0과 1은 패스
        if (num <= 1)
            return;
        
        for (int k = 2; k * k <= num; ++k)
        {
            if (num % k == 0)
                return;
        }
        
        ++answer;
        return;
    }
    
    for (int i = 0; i < allNumbers.size(); ++i)
    {
        if (used[i] == false)
        {
            used[i] = true;
            result += allNumbers[i];
            
            Check(len);
            
            result.pop_back();
            used[i] = false;
        }
    }
}

int solution(string numbers)
{
    allNumbers = numbers;
  
    for (int len = 1; len <= allNumbers.size(); ++len)
        Check(len);
    
    return answer;
}

 

---

참고

-소수

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)

 

-에라토스테네스의 체 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4