say repository

[프로그래머스] 소수 찾기 c++ 본문

알고리즘 문제 풀이/프로그래머스

[프로그래머스] 소수 찾기 c++

부끄러엇피치 2022. 3. 17. 22:23
728x90

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

출처:프로그래머스

 

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

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

programmers.co.kr

 

#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <iostream>
using namespace std;

set<int> numberSet;
//에라토스테네스의 체
bool isPrime(int n){
    if (n<2)
        return false;
    for (int i=2; i<=sqrt(n); i++){
        if (n%i == 0)
            return false;
    }
    return true;
}
//numbers로 숫자조합 만들기 -> numberSet 셋에 삽입
void makeCombination(string comb, string others){
    if (comb != "")
        numberSet.insert(stoi(comb)); //string to int
    
    for (int i=0; i<others.size(); i++)
        //재귀함수
        makeCombination(comb + others[i], others.substr(0,i) + others.substr(i+1));
}
int solution(string numbers) {
    int answer = 0;
    //numbers로 가능한 숫자 조합 만들기
    makeCombination("", numbers);

    set<int>::iterator iter;
    for(iter = numberSet.begin(); iter!=numberSet.end(); iter++){
        if(isPrime(*iter))
            answer++;
    }
    return answer;
}

 

python으로 준비하다가 c++하니까 너무 헷갈린다..ㅋㅋㅋㅋㅋ ㅠㅠ

저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 타겟 넘버 c++  (0) 2022.03.18
[프로그래머스] 카펫 c++  (0) 2022.03.17
[프로그래머스] 모의고사 c++  (0) 2022.03.17
[프로그래머스] 우유와 요거트가 담긴 장바구니 mysql (*)  (0) 2022.02.11
[프로그래머스] 헤비 유저가 소유한 장소 MYSQL (*)  (0) 2022.02.11
'알고리즘 문제 풀이/프로그래머스' Related Articles more