프로그래머스 완전탐색 소수찾기 c++ 풀이

 

문제 풀이

 

문제 보고 할 일 정리

1. 소수인지 판단하는 함수 만들기

2. 완전탐색하는 로직 만들기

3. 중복 제거하는 로직 만들기

 

1, 3은 간단했으나 완전탐색 되도록하는 로직 만드는게 까다로웠다.

1. 소수인지 판단하는 함수 만들기

간단하다.. 더 작은 숫자로 다 나눠서 떨어지는게 하나라도 있으면 false 리턴하면 됨

bool isPrime(int number)
{
    if (number < 2)
        return false;
    for (int div = 2; div < number / div + 1; ++div)
        if (number % div == 0)
            return false;
    return true;
}

 

2. 완전탐색하는 로직 만들기

완전탐색 문제를 풀 때 나는 보통 재귀로 푸는 편이어서, 이번에도 재귀로 생각을 해봤다.

재귀로 문제를 풀 때 중요한 것은 '이번' 시행과 '다음' 시행의 연관성을 생각해서 1. 각 시행에 필요한 것 (함수 인자) 2. 각 시행의 동작 3. 완료 조건, 동작 을 정하는 것이다.

3. 일단 종료 조건에서는 당연히 만들어진 숫자를 배열에 넣어야 할 것이다.
2. 각 시행에서는 해당 자릿수에 들어갈 숫자를 남은 숫자만큼의 경우의 수로 넣어준다
1. 그러려면 각 시행에는 남은 자릿수, 해당 시점까지 만들어진 숫자, 남은 숫자(종이 조각의), 그리고 종료조건에서 숫자를 저장할 배열의 주소일 것이다.

void recursive(int remainingDigits, int number, vector<int> numbers, vector<int> &primeNumbers)
{
    if (remainingDigits == 0)
    {
        if (isPrime(number))
            primeNumbers.push_back(number);
        return;
    }

    for (int i = 0; i < numbers.size(); i++)
    {
        vector<int> temp(numbers);
        temp.erase(temp.begin() + i);
        recursive(remainingDigits - 1, number * 10 + numbers[i], temp, primeNumbers);
    }
}

 

 

 

3. 중복 제거하는 로직 만들기

sort, unique, erase를 활용하는 방법을 서치해서 찾았다.

sort(primeNumbers.begin(), primeNumbers.end());
primeNumbers.erase(unique(primeNumbers.begin(), primeNumbers.end()), primeNumbers.end());

 

 

정답 코드

bool isPrime(int number)
{
    if (number < 2)
        return false;
    for (int div = 2; div < number / div + 1; ++div)
        if (number % div == 0)
            return false;
    return true;
}

void recursive(int remainingDigits, int number, vector<int> numbers, vector<int> &primeNumbers)
{
    if (remainingDigits == 0)
    {
        if (isPrime(number))
            primeNumbers.push_back(number);
        return;
    }

    for (int i = 0; i < numbers.size(); i++)
    {
        vector<int> temp(numbers);
        temp.erase(temp.begin() + i);
        recursive(remainingDigits - 1, number * 10 + numbers[i], temp, primeNumbers);
    }
}

int solution(string numbers)
{
    vector<int> primeNumbers;
    vector<int> numbersToVector;

    for (int i = 0; i < numbers.size(); ++i)
        numbersToVector.push_back(numbers[i] - '0');

    for (int digits = numbers.size(); digits > 0; digits--)
        recursive(digits, 0, numbersToVector, primeNumbers);

    sort(primeNumbers.begin(), primeNumbers.end());
    primeNumbers.erase(unique(primeNumbers.begin(), primeNumbers.end()), primeNumbers.end());

    return primeNumbers.size();
}

 

결과

 

 

 

다른 사람의 코드

딱히 참고할 만한게 없어서 안가져왔음