프로그래머스(완전탐색; 소수 찾기) c++

문제 설명

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

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

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

#include <string>
#include <vector>
#include <set>                          // 중복 방지를 위함

using namespace std;

set<int> numSet;                        // 수열들의 조합을 저장(중복방지)
bool bvistied[8] = {false, };           // 방문했던 수열의 위치를 탐색하지 않도록 함 

void dfs(string numbers, string picked)
{
    if(!picked.empty())
        numSet.insert(stoi(picked));
    
    for(int i = 0; i < numbers.size(); ++i)
    {
        if(bvistied[i]) continue;
        bvistied[i] = true;
        dfs(numbers, picked+numbers[i]);            // 사용하지 않은 수열을 기준으로 재귀적으로 호출하여 계속 붙여나감
        bvistied[i] = false;                        // 탐색이 끝나면 다음 수열을 기준으로 탐색을 할 수 있게 false로 변경 
    }
}

bool isPrime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i*i<=n; ++i)         // 약수까지 거름
    {
        if(n % i == 0 ) return false;
    }
    return true;
}

int solution(string numbers) {
    
    numSet.clear();
    dfs(numbers, "");
    
    int answer = 0;
    for(int n : numSet)
    {
        if(isPrime(n))
            ++answer;
    }
    return answer;
}

 

해설:

첫번째: string으로 타입으로 되있는 타입을 변경하기 위해서 stoi(value)를 사용하여 string->int 값으로 변경해준다("011"->"11", "0011" -> "11" 로 변경하는걸 알 수 있듯이 맨앞자리 0은 제외 시킨다).

두번째: 중복 방지를 위해 set과 bvistied을 이용한다. set은 중복 입력 방지이다. 배열에 똑같은 값의 원소가 들어오면 없앤다(#include <set>을 포함시켜야 한다). bvistied는 탐색 중복 방지이다. 반복문을 통해 기존에 탐색했던 배열들을 넣고 해당 수열의 탐색이 끝나면 다시 false로 바꿔 다음 수열이 탐색할 수 있게 전환해준다.

세번째: dfs(깊이 우선 탐색) 을 이용하여  재귀적으로 끝까지 범위를 탐색하며 picked+number[i]를 추가하여 모든 경우의 수를 파악하여 넣어준다.

네번째: isPrime 함수를 통해 소수 검사를 실행하고 i*i를 통해 배수의 오류도 방지해준다.