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

소수 찾기

문제 링크

소수 찾기

분석

주어진 숫자로 만들 수 있는 모든 숫자 조합을 만든다.
그중에서 소수인 숫자의 개수를 구한다.

서로 다른 길이의 숫자 조합을 모두 만들어야 합니다.
순열 생성 함수(next_permutation)나 백트래킹을 사용해 숫자의 조합을 생성할 수 있습니다.

서로 다른 조합을 만들다 보면 중복된 숫자가 나올 수 있습니다.
예를 들어, "11"이 주어지면 숫자 11이 중복으로 생성될 수 있으므로 중복을 제거해주어야 합니다.

조합된 숫자가 소수인지 확인해주어야 합니다.

풀이

#include <string>
#include <set>
#include <algorithm>

using namespace std;

// 소수 판별 함수
// 제곱근까지만 나누는 방법
bool isPrime(int num)
{
    if (num < 2) return false;
    
    for (int i = 2; i * i <= num; ++i)
    {
        if (num % i == 0) return false;
    }
    
    return true;
}

int solution(string numbers) {
    int answer = 0;
    
    // 중복을 제거한 숫자 조합
    set<int> uniqueNumbers;
    
    // 순열 함수를 사용하기 위해 정렬
    sort(numbers.begin(), numbers.end());
    
    // 순열을 사용해 나올 수 있는 숫자 조합 생성
    do
    {
        // 수열로 만들어진 숫자 조합을 부분 문자열을 사용해 분리
        for (int len = 1; len <= numbers.size(); ++len)
        {
            int num = stoi(numbers.substr(0, len));
            uniqueNumbers.insert(num);
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    // 소수 개수 세기
    for (int num : uniqueNumbers)
    {
        if (isPrime(num))
        {
            ++answer;
        }
    }
    
    return answer;
}

"123"을 예시로 순열을 사용해 나올 수 있는 숫자 조합을 살펴보면 다음과 같습니다.

123
132
213
231
312
321

각 순열에서 numbers.substr(0, len)을 통해 부분 문자열을 추출하는 예시는 다음과 같습니다.

순열	len	numbers.substr(0, len)
“123”	1	“1”
“123”	2	“12”
“123”	3	“123”
“132”	1	“1”
“132”	2	“13”
“132”	3	“132”
“213”	1	“2”
“213”	2	“21”
“213”	3	“213”

이후 순열에도 같은 동작을 수행합니다.

성능 요약

시간 복잡도는 $O(N! \times max(N^2, \sqrt{M}))$입니다.

• 정렬 $O(N \ log \ N)$
• 순열 생성 $O(N!)$
• 문자열에서 숫자로 형변환 $O(N^2)$
• 소수 판별 $O(N! \times \sqrt{M})$
• $O(N \log N + N! \times N^2 + N! \times \sqrt{M})$

공간 복잡도는 $O(N! * N)$입니다.

• 중복 제거된 숫자 조합을 저장하는 set<int> uniqueNumbers $O(N! * N)$

테스트 1 〉 통과 (0.02ms, 4.22MB)
테스트 2 〉 통과 (0.82ms, 4.21MB)
테스트 3 〉 통과 (0.02ms, 4.14MB)
테스트 4 〉 통과 (0.03ms, 4.2MB)
테스트 5 〉 통과 (0.02ms, 4.14MB)
테스트 6 〉 통과 (0.02ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.25MB)
테스트 8 〉 통과 (0.02ms, 4.14MB)
테스트 9 〉 통과 (0.01ms, 3.73MB)
테스트 10 〉 통과 (0.69ms, 4.17MB)
테스트 11 〉 통과 (0.14ms, 3.68MB)
테스트 12 〉 통과 (0.04ms, 4.21MB)