프로그래머스 / level.2 / 소수 찾기(C++)

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

프로그래머스

문제 설명

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

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

내 해답

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

using namespace std;

// 소수 검사
bool isPrime(int n)
{
    // 2미만 소수는 없다.
    if(n < 2)
        return false;
    
    // 2부터 n의 제곱근까지 소수 검사
    for(int i = 2; i <= sqrt(n); ++i)
    {
        if(n%i == 0)
            return false;
    }
    
    return true;
}

int solution(string numbers) {
    int answer = 0;
    set<int>ans{};
    
    // 입력 문자열 정렬
    sort(numbers.begin(), numbers.end());

    
    // numbers 순열의 첫번째 문자부터 문자를 누적해가며 소수인지 비교한다. 
    do
    {
        string tmp;
        for(int i = 0; i < numbers.size(); ++i)
        {
            tmp += numbers[i];
            if(isPrime(stoi(tmp))) 
                ans.insert(stoi(tmp));      // set이므로 소수인 숫자 조합들을 중복없이 담는다.
        }
    }
    while(next_permutation(numbers.begin(), numbers.end()));
     
    answer = ans.size();
        
    return answer;
}

이 문제는 '소수 판별 하기'와 '문자를 조합하여 숫자 찾기' 가 관건인 문제였다.

 

1. 소수 판별하기

예를 들어 16이라는 수의 약수는 다음과 같다.

• 1 X 16 = 16 _________
• 2 X 8 = 16   ___               |
• 4 X 4 = 16         |   대칭   대칭
• 8 X 2 = 16   ___               |
• 16 X 1 = 16 _________

가운데 약수 4를 기준으로 각 등식이 대칭적인 형태를 보인다는 것을 알 수 있다.
예를 들어 2 X 8 = 16은 8 X 2 = 16과 대칭이다.

그렇기에 특정한 자연수 X가 소수인지 확인하기 위하여 바로 가운데 약수까지만 나누어 떨어지는지 확인하면 된다.

다시 말해 제곱근까지만(가운데 약수까지만) 확인하면 된다!!

 

2. 문자를 조합하여 숫자 찾기

algorithm 라이브러리의 next_permutation 이라는 함수를 잘 사용하면 쉽게 해결할 수 있다.

-  next_permutation 이란?

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

next_permutation 함수에 벡터의 iterator 혹은 배열의 주소를 넣으면 다음 순열(1-2-3-4의 다음 순열은 1-2-4-3)의 결과가 벡터나 배열에 적용된다.

- next_permutation 의 반환값

성공적으로 순열을 생성했다면 true를 반환하고

모든 순열을 생성해 다음 순열이 없다면 false를 반환한다.