소수 찾기(20분)

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

지하철이라 정확히 몇 분만에 풀었는지 예상하여 기록.
구현 아이디어 3분 구현 17분

풀이

DFS를 활용하여 가능한 조합을 구하는데 이전에 검사한 수일 경우 return 할 수 있게 map 컨테이너를 사용하여 검사한다.
예: 011과 11은 같은 수이기 때문에 중복 검사해서는 안된다.

#include <string>
#include <vector>
#include <iostream>
#include <map>

using namespace std;
int comb[7], answer;
int ch[7];
map<int, int> m;

void DFS(int L, int e, const string& numbers)
{
    if(L == e)
    {
        string str = "";   
        for(int i = 0; i < e; ++i) str += (comb[i] + '0');
        
        int number = stoi(str);
        if(number < 2) return;
        
        // number가 이전에 확인한 숫자인지 검사 필요.
        if(m[number]) return;
        m[number]++;
        
        for(int i = 2; i < number; ++i)
            if(number % i == 0) return;
        
        answer++;
    }
    else
    {
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(ch[i] == 0)
            {
                ch[i] = 1;
                comb[L] = numbers[i] - '0';
                DFS(L + 1, e, numbers);
                ch[i] = 0;
            }
        }
    }
}

int solution(string numbers) {
    int N = numbers.size();
    
    for(int i = 1; i <= N; ++i)
    {
        // 레벨, 만들 자리 수, 원본 문자열
        DFS(0, i, numbers);
    }
    
    return answer;
}

---

개인적인 감상. 분명 소수를 더 효율적으로 판단하는 구현법을 알고 있었는데 증발해 버렸다. 복습은 정말 중요하다. 학원에 갔다가 집에 가는 지하철에서 더 효율적인 소수 판별법을 복습하여 글에 추가해야겠다.

---

소수 판별

어떤 수가 소수라는 것은 1과 자기 자신을 제외하고 약수가 없다는 뜻이다. 그리고 약수는 그 수의 제곱근까지만 검사하면 된다.

예: 숫자가 36이라면, 36은 1 * 36, 2 * 18, 3 * 12, 4 * 9, 6 * 6의 경우가 있다. 나머지는 9 * 4와 같이 뒤집은 경우일 것이기 때문에 결론적으로 6까지만 검사하면 36이라는 수에 약수가 있는지 검사할 수 있다.

해당 소수 판별법을 이용하여 문제를 다시 풀어봤다. 채점 시간이 비약적으로 줄어들었다. for문에서 조건만 살짝 수정했다.

#include <string>
#include <vector>
#include <iostream>
#include <map>

using namespace std;
int comb[7], answer;
int ch[7];
map<int, int> m;

void DFS(int L, int e, const string& numbers)
{
    if(L == e)
    {
        string str = "";   
        for(int i = 0; i < e; ++i) str += (comb[i] + '0');
        
        int number = stoi(str);
        if(number < 2) return;
        
        if(m[number]) return;
        m[number]++;
        
        // 바뀐 부분.
        for(int i = 2; i*i <= number; ++i)
            if(number % i == 0) return;
        
        answer++;
    }
    else
    {
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(ch[i] == 0)
            {
                ch[i] = 1;
                comb[L] = numbers[i] - '0';
                DFS(L + 1, e, numbers);
                ch[i] = 0;
            }
        }
    }
}

int solution(string numbers) {
    int N = numbers.size();
    
    for(int i = 1; i <= N; ++i)
    {
        DFS(0, i, numbers);
    }
    
    return answer;
}