Programmers <소수찾기>

Yerim·2021년 9월 13일
0

Programmers

목록 보기
12/12

Level 2


문제 설명

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

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


제한 사항

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

입출력 예

numbersreturn
"17"3

작성 코드

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

using namespace std;

bool sosu(int n) {   // 소수 판별 함수
    if(n < 2)
        return false;
    int s = (int) sqrt(n);   // 루트 n
    for(int i=2; i <= s; i++) {
        if(n % i == 0)
            return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<int> numbersInt;
    vector<int> finalInt;
    
    for(int i=0; i<numbers[i]; i++)
        numbersInt.push_back(numbers[i] - '0');
    
    sort(numbersInt.begin(), numbersInt.end());
    
    do {
        for(int i=0; i<=numbersInt.size(); i++) {
            int temp = 0;
            for(int j=0; j<i; j++) {
                temp = (temp*10) + numbersInt[j];
                finalInt.push_back(temp);
            }
        }
    } while(next_permutation(numbersInt.begin(), numbersInt.end()));
    
    sort(finalInt.begin(), finalInt.end());
    finalInt.erase(unique(finalInt.begin(), finalInt.end()), finalInt.end());
    
    for(int i=0; i<finalInt.size(); i++) {
        if(sosu(finalInt[i]))
            answer++;
    }
    
    return answer;
}

📌

  • 모든 경우의 수를 찾기 위해서 주어진 수들을 이용하여 순열을 만들 수 있다. ➡ next_permutation
  • 각 순열마다 최소 자릿수(1)부터 최대 자릿수까지 수를 만들어 새로운 vector에 push
  • 매 순열마다 숫자를 생성하여 vector에 push하므로 중복된 수가 존재할 수 있다.
  • 이를 sort, unique를 사용하여 erase
    • sort 후 unique를 사용하면 vector의 중복된 요소를 vector의 뒤로 보낸다
    • unique는 쓰레기값의 시작 index 반환
    • 해당 index부터 마지막 index까지 erase
  • 중복값 제거 후 vector에 남아있는 수가 주어진 문자열로 만들 수 있는 수의 수다.
  • 해당 수에서 소수를 찾아서 갯수 반환
  • 문자열 조합을 통해 얻을 수 있는 모든 경우의수를 찾을 때 순열을 사용하는 것도 방법!
profile
Backend-Developer

0개의 댓글