[Programmers] 소수 찾기

👀 문제 설명

문제

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

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

✍🏻풀이

일단 순열을 사용하는건 알겠는데, 이걸 코드로 어떻게 구현하느냐가 너무 어려웠다.

처음에는 재귀를 사용해서 숫자를 만들어, 숫자가 붙을 때마다 newNums 벡터에 넣었는데, 숫자가 이상하게 만들어졌다..ㅠ

(코드 놔둘걸,, 다 지워버림)

아무튼 그래서 검색해보니까, algorithm 헤더에 next_permutation 함수를 사용하면 쉽게 순열을 구할 수 있다더라,,

 

next_permutation 함수

bool next_permutation(BidirectionIterator first, BidirectionIterator last);

-> 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝

bool next_permutation(BidirectionIterator first, BidirectionIterator last, Compare comp);

-> 이처럼 세번째 인자에 직접 비교함수를 넣어줘도 된다.

 

코드

//
//  Programmers_42839.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/10/26.
//  Copyright © 2020 조수민. All rights reserved.
//
//  소수 찾기(https://programmers.co.kr/learn/courses/30/lessons/42839)

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

// 소수 판별 함수
bool isPrime(int n) {
    if (n == 2) // 2는 소수이다
        return true;

    if (n == 1) // 1은 소수가 아니다
        return false;
    
    if (n % 2 == 0) // 소수는 다 홀수이므로, 짝수는 소수가 아니다
        return false;
    
    /**
     앞에서 짝수는 다 걸러줬으므로,
     홀수로만 나눠본다.
     n보다 작은 모든 홀수로 나눴을 때, 나누어 떨어지지 않는다면
     소수이다
     */
    for (int i = 3; i < n; i += 2) {
        if (n % i == 0) // 나누어떨어짐 = 소수가 아니다
            return false;
    }
    
    return true;
}

/**
 algorithm 헤더에 있는 next_permutation 함수를 사용하면 순열을 쉽게 구할 수 있다.
 */
int solution(string numbers) {
    int answer = 0;
    
    // 순열 구하기
    vector<int> newNums;
    sort(numbers.begin(), numbers.end());
    
    do {
        for (int i = 1; i <= numbers.size(); i++) {
            
            newNums.push_back(stoi(numbers.substr(0, i)));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));
    
    // newNums 벡터의 중복을 제거하기 위해 unique와 erase를 사용한다.
    // 이 때 주의점은, sort를 한 후 사용해줘야 중복된 값이 제대로 삭제된다.
    sort(newNums.begin(), newNums.end());
    newNums.erase(unique(newNums.begin(), newNums.end()), newNums.end());
    
    // 소수인지 판별, 소수가 맞으면 answer + 1
    for (int i = 0; i < newNums.size(); i++) {
        if (isPrime(newNums.at(i)))
            answer++;
    }
    
    return answer;
}

int main() {
    cout << solution("17") << endl;
    
    return 0;
}