[프로그래머스 - 완전탐색] 소수 찾기 (C++)

programmers.co.kr/learn/courses/30/lessons/42839

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

문제 설명

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

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

 

제한사항

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

입출력 예

numbers	return
17	3
011	2

입출력 예 설명

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

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

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

풀이

 

1) 문자열로 들어온 숫자를 int 배열로 바꿔줌

2) dfs로 숫자 조합을 만들어서 made 벡터에 추가

3) made 벡터에서 중복된 수 제거 (정렬 후 unique 함수로 중복된 원소를 뒤로 보내준 뒤 erase)

4) 소수 개수 구하기

 

*소수 판별 알고리즘

 - 0,1은 false, 2는 true

 - n을 i로 나눈 나머지가 0이면 false (i는 2이상이고 제곱이 n이하인 자연수)

 

소수 판별 알고리즘에는 이 방법 외에도 '에라토스테네스의 체'라는 방법이 있음

(참고 : ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool visit[10];
int tmp[10];
int num[10];
int len;
vector<int> made;

bool isPrime(int n){
    if(n<2) return false;
    if(n==2) return true;
    for(int i=2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    return true;
}

void dfs(int depth, int max){
    if(depth >= max) {
        int madeNum=0;
        for(int i=0;i<depth;i++){
            madeNum*=10;
            madeNum+=tmp[i];
        }
        made.push_back(madeNum);
        return;
    }
    for(int i=0;i<len;i++){
        if(visit[i]) continue;
        visit[i]=true;
        tmp[depth]=num[i];
        dfs(depth+1,max);
        visit[i]=false;
        tmp[depth]=0;
    }
}

int solution(string numbers) {
    int answer = 0;
    len = numbers.length();
    for(int i=0;i<len;i++){
        num[i]=numbers[i]-'0';
    }
    for(int i=1;i<=len;i++){
        dfs(0,i);
    }
    // 중복 제거
    sort(made.begin(),made.end());
    made.erase(unique(made.begin(),made.end()),made.end());
    // 소수 개수 구하기
    int cnt=0;
    for(int i=0; i<made.size(); i++){
        if(isPrime(made[i])) cnt++;
    }
    answer = cnt;
    return answer;
}