[프로그래머스] 소수 찾기 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 소수 찾기 문제입니다.

 

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

 

numbers	return	example..
"17"	3	7, 17, 71
"011"	2	11, 101

 

 

 

해결 과정

 

주어진 문자열의 숫자들로 구할 수 있는 모든 부분집합들 구합니다.

ex) "17" => 1, 17, 71

 

부분집합을 구하는 과정에서 부분집합의 앞자리가 0이거나 부분집합이 0이나 1인(1은 소수에 포함x) 경우를 제외하고

구할 수 있었던 모든 부분집합을 배열에 저장합니다. 이때 제가 구현한 방법에서는 문자열 내에 중복되는 숫자가 있을 시

중복된 부분집합을 가질 수있어서, 부분집합을저장한 배열의 중복된 부분을 제거합니다.(erase unique 기법을 사용하였습니다.) 이후 소수인지를 판별 함수를 통해 부분집합배열을 판단하고 판단되어진 횟수를 반환합니다.

 

 

 

 

코드 전문

 

 

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

using namespace std;

vector<int> vec;

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

void comb(string s, int pos, string cur_s)
{
    if (pos == s.size()) 
    {
        if (cur_s[0] == 0 || stoi(cur_s) == 0 || stoi(cur_s) == 1) return;
        vec.emplace_back(stoi(cur_s));
        return;
    }
    comb(s, pos+1, cur_s+s[pos]);
    comb(s, pos+1, cur_s);
}

int solution(string numbers) {
    int answer = 0;
    if (numbers == "0") return 0;
    
    // take vector all subset
    sort(numbers.begin(), numbers.end());
    do
    {
        comb(numbers, 0, "");
    }
    while (next_permutation(numbers.begin(), numbers.end()));

    // remove overlap
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for (auto num : vec)
        if (isPrime(num) == true) answer++;
    
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

부분집합을 만들어보았고 중복된 부분을 제거하기 위해 erase unique 기법을 사용하였습니다. 

어제 erase remove idiom에 관한 글을 적었는데 그와 비슷한 맥락인 이 기법을 사용할 수 있어 재밌었습니다.

 

소수 부분도 재밌었습니다. 에라스토네스의 체라는 것도 알게 되었습니다.

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.