Programmers 소수 찾기 C++

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

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

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

programmers level 2 소수찾기 문제입니다.

 

예를 들어서 문제를 설명하겠습니다.

 

예제에 있는 "17"의 경우 1, 7을 이용해서 수를 만들 수 있고

이 때 소수를 만들 수 있는 경우는 7, 17, 71 이렇게 3가지입니다.

 

결국 String이 주어지면 각 자릿수를 이용해서 모든 수를 조합해보고, 소수를 만들 수 있는 경우가 몆개냐! 를 묻습니다.

 

이 문제를 풀기 위해서 에라토스테네스의 체 알고리즘을 사용했습니다.

이정도 알고리즘은 기본 중의 기본이니 꼭 사용할 줄 아셔야합니다.

(에라토스테네스 :  https://junho0956.tistory.com/35)

 

좀 더 소수에 근접하게 수를 빠르게 만들 수 있는 방법이 있을까 고민해봤는데.. 떠오르질 않더라구요

그래서 완전탐색과 같이 모든 경우의 수에 접근했습니다.

 

저는 DFS를 이용해서 아래와 같이 접근했습니다! (백트래킹 이라고 할 수 있겠네요)

 

dfs(현재까지 만든 수, 더 사용할 수 있는 수)

 

dfs 과정마다 현재까지 만든 수를 소수인지 확인해주는 작업을 꼭 해주시고,

같은 수가 중복될 수 있으니 찾은 숫자는 따로 처리해주세요!

 

설명은 주석을 달아놓았으니, 보시면 바로 이해되실껍니다~

#include <string>
#include <vector>
#include <iostream>
#define e7 10000000 // e7 : 1e7이 사용이 안되서 만들었어요. 1천만 입니다
using namespace std;

bool sosu[e7]; // 소수는 e7까지 접근가능합니다
bool find_it[e7]; // 소수를 찾은 경우 사용했음을 나타내기 위해 사용합니다
bool use[7]; // 각 자리수에 접근할 녀석이에요
string str; // 스트링은 전역으로 사용했습니다

void make_eratos() { // 에라토스테네스의 체
    for (int i = 2; i < e7; i++) sosu[i] = true;
    for (int i = 2; i * i < e7; i++)
        if (sosu[i])
            for (int k = i * i; k < e7; k += i) sosu[k] = false;
}

int dfs(int make_num, int able) { // 탐색부분
    // 더이상 사용할 수 있는 수가 없으면 소수인지 바로 판단해주세요
    if (!able) {
        if (sosu[make_num]) {
            if (find_it[make_num]) return 0;
            find_it[make_num] = 1;
            return 1;
        }
        else return 0;
    }
    
    int ret = 0;
    // 항상 현재까지 만든 수가 소수인지 확인하는 작업!
    if (sosu[make_num] && !find_it[make_num]) find_it[make_num] = 1, ret++;

    for (int i = 0; i < str.size(); i++) { // 모든 수에 접근합니다.
        if (!use[i]) { // i번째 자리수를 사용안했다면?
            int join_num = make_num; // 새로운 수를 만들어주세요
            join_num *= 10;
            join_num += str[i] - '0';
            use[i] = 1; // 이 자리를 사용했음을 나타냅니다
            ret += dfs(join_num, able - 1);
            use[i] = 0; // 이 자리의 사용이 끝났음을 나타냅니다
        }
    }

    return ret;
}

int solution(string numbers) {

    str = numbers;
    make_eratos(); // 일단 소수부터 만들게요
    return dfs(0, numbers.size());

}