프로그래머스 완전탐색 소수찾기

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

나의 코드

이번 코드는 조금 어려웠다.

소수를 판별하기 위해 에라토스테너스의 체라는 공식을 사용하기도 하였고

무작위 숫자를 만들기 위해 permutation이라는 새로운 함수를 사용해보았다.

 

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

using namespace std;

bool findsosu(int n) {
    //소수인지 확인하는 코드
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;
    return true;
}

int solution(string numbers) {
    int answer = 0;
    //split 코드
    vector<char> ch_num;
    vector<int> nums;
    for (int i = 0; i < numbers.size();i++) {
        ch_num.push_back(numbers[i]);
    }
    sort(ch_num.begin(), ch_num.end());

    do {
        string tmp = "";
        for (int i = 0; i < ch_num.size();i++) {
            tmp.push_back(ch_num[i]);
            nums.push_back(stoi(tmp));
        }
    } while (next_permutation(ch_num.begin(), ch_num.end()));

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    for (int n : nums) {
        if (findsosu(n)) answer++;
    }
    return answer;
}

주석 있는 버전

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

using namespace std;

bool findsosu(int n) {
    //소수인지 확인하는 코드 = > 에라토스테너스의 체 사용
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++) //sqrt 루트
        if (n % i == 0) return false;
    return true;
}

int solution(string numbers) {
    int answer = 0;
    //split 코드
    vector<char> ch_num;
    vector<int> nums;
    for (int i = 0; i < numbers.size();i++) {
        ch_num.push_back(numbers[i]);
    }
    sort(ch_num.begin(), ch_num.end());

    do {
        string tmp = "";
        for (int i = 0; i < ch_num.size();i++) { //i자리 수의 숫자 생성
            tmp.push_back(ch_num[i]);
            nums.push_back(stoi(tmp));
        }
    } while (next_permutation(ch_num.begin(), ch_num.end())); //무작위 수 생성
    
    sort(nums.begin(), nums.end()); //정렬
    nums.erase(unique(nums.begin(), nums.end()), nums.end()); //중복되는 수 제거

    for (int n : nums) { //소수인지 판단
        if (findsosu(n)) answer++;
    }
    return answer;
}

 

---

다른 풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

bool isPrime(int number) //소수인지 확인
{
    if (number == 1) //1인경우 소수x
        return false;
    if (number == 2) //2인 경우 소수o
        return true;
    if (number % 2 == 0)	//2로 나누어 떨어지면 소수x
        return false;

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

    return isPrime;
}

bool compare(char a, char b) //내림차순 정렬
{
    return a > b;
}

int solution(string numbers) {
    int answer = 0;
    string temp;
    temp = numbers;

    sort(temp.begin(), temp.end(),compare); //temp(numbers) 내림차순 정렬

    vector<bool> prime(std::stoi(temp)+1);

    prime[0] = false;
    for (long long i = 1; i < prime.size(); i++) //각 index에 해당하는 한자리 수가 소수인지 판단
    {
        prime[i] = isPrime(i);
    }

    string s, sub;
    s = numbers;

    sort(s.begin(), s.end()); //s(numbers) 정렬
    set<int> primes; 
    int l = s.size();
    do {
        for (int i = 1; i <= l; i++) //i자리 수 생성
        {
            sub = s.substr(0, i);
            if (prime[std::stoi(sub)]) //만약 sub가 set에 저장되있지 x => insert
            {
                primes.insert(std::stoi(sub));
            }
        }
    } while (next_permutation(s.begin(), s.end()));

    answer = primes.size(); //set에 저장된 숫자 개수 출력
    return answer;
}

 기계과괜히 왔어 , - , - , 심재훈 , Jaehun Ryu 외 3 명의 코드입니다.

 

너무 어렵다... 같은 느낌의 알고리즘을 사용하였으나 코드가 이렇게 다를 수 있다는 것을 느꼈다.

---

참고 블로그
notepad96.tistory.com/entry/C-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0