프로그래머스 Level 2 소수찾기

소수찾기 (프로그래머스 Level 2)

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

재귀와 백트래킹을 이용한 완전 탐색으로 풀었다
다소 오랜만에 이러한 알고리즘을 풀었기에 오히려 재미있었다

일단 백트래킹에 대하여 가볍게 복습하자면,
조건의 부합 여부를 확인하고,
조건에 맞지 않으면 ‘이전’의 다른 선택지를 시도한다는 점이다
(브루트 포스보다 조금 더 효율적인 편, 브루트 포스는 이러한 최적화가 없다)
(또한 트리 탐색에 어울리기에, BFS 및 DFS 등으로도 응용되어 구현된다)
(결국 요점은 ‘조건의 판별’ 과 ‘이전 분기로 돌아감’ 이 포함되었는지의 여부)

이 문제는 백트래킹을 통해, 가능한 모든 조합의 수를 구하며,
이를 set에 넣어 중복은 제거하였다

이후, set 내부를 돌며, 소수인 수를 세어 문제를 해결하였다

Code

#include <string>
#include <vector>
#include<math.h>
#include<memory.h>
#include<set>

using namespace std;

void startRecur(string num, int size, set<int>& s);
void recur(const string& num, string& temp, bool* bArr, int size, set<int>& s);

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

    if (n < 4)
        return true;

    int sqn = sqrt(n);

    for (int i = 2; i <= sqn + 1; i++)
    {
        if (n % i == 0)
            return false;
    }

    return true;
}

int solution(string numbers) {
    int answer = 0;
    int size = numbers.size();
    set<int> s;

    for (int i = 1; i <= size; i++)
    {
        startRecur(numbers, i, s);
    }

    // 여기서 s 돌면서 체크하기
    for (auto a : s)
    {
        if (isPrime(a))
            answer++;
    }

    int b = 0;

    return answer;
}

// 재귀 시작 용
void startRecur(string num, int size, set<int>& s)
{
    // num의 각 요소들을 시작으로 for문을 돌리고
    // 방문 관련 bool 배열도 이쪽에서 관리한다
    int nSize = num.size();
    bool* bVisit = new bool[nSize];
    memset(bVisit, 0, sizeof(bool) * nSize);
    
    string temp = "";

    for (int i = 0; i < nSize; i++)
    {
        // 여기서 처음 시작하는 부분에 bVisit를 true로 만들어 주고 아래쪽 함수에 넘겨주기
        bVisit[i] = true;
        temp += num[i];
        recur(num,temp, bVisit,size,s);
        bVisit[i] = false;
        temp = "";
    }

    delete[] bVisit;
}

// 재귀 반복 용
void recur(const string& num,string& temp,bool* bArr,int size, set<int>& s)
{
    // size와 num의 길이가 같으면 break 하면서 return 해야 한다
    // 그리고 나서 check
    if (temp.size() == size)
    {
        int r = stoi(temp);
        s.insert(r);
        return;
    }

    int nSize = num.size();
    
    for (int i = 0; i < nSize; i++)
    {
        // 이미 탐색이 완료된 부분
        if (bArr[i] == true)
            continue;

        bArr[i] = true;
        string originTemp = temp;
        temp += num[i];
        recur(num, temp, bArr, size, s);
        temp = originTemp;
        bArr[i] = false;
    }
}

해결 아이디어

1. 가능한 모든 경우의 수를 구하여 해당 수가 소수인지 판별하는 것이 목적
2. 재귀를 돌면서 ‘현재 방문중인 경우’ bool 배열을 체크
   재귀에 들어갈때, true를 체크하고 나갈 때 false로 풀어주는 방식으로
   가능한 모든 범위를 탐색한다
   
3. 마지막으로 구한 수를 set에 넣어준다
   
4. 재귀가 끝난 후, set 내부를 탐색하며 소수인지 확인
   
5. 소수라면 answer에 1을 더해준다