프로그래머스_코딩테스트 연습_완전탐색_소수찾기

완전탐색 - 소수찾기

작성언어 C++

 

• 소수 찾기

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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. C++ STL 알고리즘에서 정렬(sort) , 순열찾아주는 (next_permutation) 함수를 활용하였음
2. 소수찾기 - 에라토스테네스의 체

3. 중복된 수 제거

 

처음에는 별 생각없이 조합가능한 자릿수 1~ n까지 구하려고했지만 만만치않다고 생각해서 바로 철회

 vector<int> arr;
 for(int i=1;i<=numbers.length();i++) //자릿수가 1이상 7이하인 숫자 만들기
 {
   if(i==1) //자릿수가 1일때
   {
     for(int j=0;j<numbers.length();j++)
     {
     	arr.push_back(numbers[j])
     }
   }
   cout<<numbers[i]<<endl;
   numbers[i]-'0'; //char to int
 }

위 코드는 따라하지말것..

 

 

 

이후 위의 풀이방법 1,2,3 을 활용해서 풀었고

중복된 수를 제거하기위해 STL 의 find 함수를 사용했다.

 

전체코드

 

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

using namespace std;

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;
}

int solution(string numbers) {
    int answer = 0;
    vector<char> ch;
    vector<int>  number;
    
    for(int i=0;i<numbers.length();i++)
        ch.push_back(numbers[i]);
    sort(ch.begin(), ch.end()); //순열 함수 사용하기위해서 정렬
    
    do{
        string temp = "";
        for(int i=0;i<ch.size();i++)
        {
            temp+=ch[i];
            auto it = find(number.begin(),number.end(),stoi(temp)); //find 함수이용 중복된 수 찾기
            if(it == number.end()) //중복된 수가 아니면 예외처리
                number.push_back(stoi(temp));
        }
    }while(next_permutation(ch.begin(),ch.end())); //순열 생성
    
    sort(number.begin(),number.end());
    
    for(int i=0;i<number.size();i++)
    {
        cout<<number[i]<<endl;
        if(isPrime(number[i]))
            answer++;
    }
    return answer;
}

 

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

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