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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

소수 찾기

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

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

문제

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

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

제한사항

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

 

풀이

입출력 예시

 

풀이

주어진 문자열에서  순열을 통해 숫자들을 만들어야한다. 그 후, 이 숫자들이 소수인지를 알아내서 수를 반환하면 된다. 수가 중복해서 만들어질 수 있으므로, 소수는 set에 저장하자.

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

using namespace std;

int solution(string numbers) {
    int answer = 0;
    vector<int> stonum;
    set<int> prime_number;
    
    for (int i = 0; i < numbers.length(); i++) {
        stonum.push_back(numbers[i] - '0');
    }
    
    return answer;
}

첫번째 예시로 보자면, 만들 수 있는 숫자의 수는 \(_2P_1\) + \(_2P_2\)가 된다. 즉, numbers의 길이만큼 반복해줘야한다.

...
    ...
    sort(stonum.begin(), stonum.end());

    for (int r = 1; r <= numbers.length(); r++) {
        do {
            string tmp = "";
            int check = 0;

            for (int i = 0; i < r; i++) {
                tmp += to_string(stonum[i]);
            }
            check = stoi(tmp);
        } while (next_permutation(stonum.begin(), stonum.end()));
    }
    ...
...

이제 check가 소수가 맞는지를 판별해야한다. 소수의 정의는 "1과 자기 자신으로만 나누어지는 자연수" 이다. 그러므로 2부터 시작해서 check - 1까지의 수 중 나머지가 0이 되는게 있다면 소수가 아니게 된다.

...
    ...
        ...
            ...
            if (check <= 1) { // 1과 0은 소수가 아님
                continue;
            }

            bool check_prime = true;
            for (int i = 2; i < check; i++) {
                if (check % i == 0) {
                    check_prime = false;
                    break;
                }
            }
            if (check_prime) {
                prime_number.insert(check);
            }
            ...
        ...
    ...
    answer = prime_number.size();
    ...
...

전체 코드

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

using namespace std;

int solution(string numbers) {
    int answer = 0;
    vector<int> stonum;
    set<int> prime_number;
    
    for (int i = 0; i < numbers.length(); i++) {
        stonum.push_back(numbers[i] - '0');
    }
    
    sort(stonum.begin(), stonum.end());

    for (int r = 1; r <= numbers.length(); r++) {
        do {
            string tmp = "";
            int check = 0;

            for (int i = 0; i < r; i++) {
                tmp += to_string(stonum[i]);
            }
            check = stoi(tmp);
            
            if (check <= 1) { // 1과 0은 소수가 아님
                continue;
            }

            bool check_prime = true;
            for (int i = 2; i < check; i++) {
                if (check % i == 0) {
                    check_prime = false;
                    break;
                }
            }
            if (check_prime) {
                prime_number.insert(check);
            }
        } while (next_permutation(stonum.begin(), stonum.end()));
    }
    
    return answer;
}

결과

 

 

---

소수를 판별할 때, check의 수가 매우 커진다면 시간이 오래 걸리게 됩니다(만약 check가 997이라면 판별 for문을 995번 돌아야 합니다!). 이를 예방해보겠습니다. 나누어 떨어지는지를 판별할 때, 2부터 check까지가 아닌, sqrt(check) 까지만 찾아보게하는 것입니다.

...
    ...
        ...
            ...
            if (check <= 1) {
                continue;
            }

            bool check_prime = true;
            for (int i = 2; i <= (int)sqrt(check); i++) {
                if (check % i == 0) {
                    check_prime = false;
                    break;
                }
            }
            if (check_prime) {
                prime_number.insert(check);
            }
            ...
        ...
    ...
    answer = prime_number.size();
    ...
...

이 방법이 가능한 이유

16을 예시로 들어보겠습니다.

16의 약수는 [ 1, 2, 4, 8, 16 ]입니다. 4를 기준으로 앞뒤로 곱해주면 16이 되는 것을 알 수 있습니다.

즉, \(sqrt{16}\)까지만 나누어 떨어지는지 판별하면 된다는 뜻입니다.

결과

수행 시간에서(특히 10번 케이스) 수정된 코드가 더 빠른 점을 알 수 있습니다.