[고득점Kit][완전 탐색] 소수 찾기 ⭐⭐

[완전 탐색] 소수 찾기

난이도 ⭐⭐

문제

내 풀이 ⭕

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

using namespace std;

set<int> allComb;

void permutation(string str, int depth, int n, int r)
{
    if (depth == r)
    {
        string temp = "";
        for(int i = 0; i < r; i++)
        {
            temp += str[i]; 
        }
        
        allComb.insert(stoi(temp));
        
        return;
    }
    
    for(int i = depth; i < n; i++)
    {
        iter_swap(str.begin() + depth, str.begin() + i);
        permutation(str, depth + 1, n, r);
        iter_swap(str.begin() + depth, str.begin() + i);
    }
}
    
int solution(string numbers) {
    int answer = 0;
    
    for(int i = 1; i <= numbers.size(); i++)  // nP1, nP2, nP3, ... nPn 구하기
    {
        permutation(numbers, 0, numbers.size(), i);  // depth는 0부터 넘겨준다. 
    }
    
    int count = 0;   // 소수 아닌 수의 개수를 셀 변수
    for(auto & num : allComb)
    {
        if (num == 0 || num == 1)  // 0 과 1 은 소수가 아니므로 count 증가시켜준 후 다음 수를 검사하기 위해 continue
        {
            count++;
            continue;
        }
        for(int i = 2; i <= sqrt(num); i++)
        {
            if (num % i == 0)  // 약수가 있다면 소수가 아니므로 count 증가시켜준 후 다음 수를 검사하기 위해 break
            {
                count++;
                break;
            }
        }
    }
    
    answer = allComb.size() - count;
    
    return answer;
}

반복문으로 순열을 구해보려고 애쓰다가 포기했던 문제.. ^ -^

• 순열을 구현하는 재귀 과정에 대한 설명은 👉 이 포스트를 참고해주세요
• 예를 들어 numbers문자열이 "011" 이라면
  • 길이가 1 인 numbers의 모든 순열 (ex. 0, 1, 1)
  • 길이가 2 인 numbers의 모든 순열 (ex. 01, 01, 10, 11, 10, 11)
  • 길이가 3 인 numbers의 모든 순열 (ex. 011, 011, 101, 110, 101, 110)
  • 즉, numbers문자열의 길이가 n이라면 nP1, nP2, nP3,… nPn 까지의 각각의 모든 순열들이 소수 검사 대상이 된다.
    • 이렇게 모든 후보들을 구한 후 소수인지만 일일이 검사해주면 된다.
• 중복이 되지 않아야 하며 0을 제외하고 0 으로 시작하는 수는 없어야 한다.
  • 순열, 즉 소수 검사 대상들을 set 컨테이너에 넣으면 중복되지 않게 관리 할 수 있다.
    • set 컨테이너는 삽입시 이미 중복되는 원소가 있다면 삽입하지 않고 무시한다.
  • 011 같이 0으로 시작하는 순열의 경우, 어차피 이들은 문자열이므로 string 헤더의 stoi 함수를 사용하면 0 으로 시작하는 문자열 순열이라도 숫자로 잘 변환되서 삽입된다.
    • stoi("011") 👉 11
  • 따라서 set 컨테이너인 allComb에 allComb.insert(stoi(temp)); 이렇게 삽입해주면 위 문제는 해결된다.
    • 순열들 중 하나를 결정 짓는 곳인 재귀의 base case인 depth == r가 될 때 위와 같이 삽입해주면 된다!
• N 의 약수는 sqrt(N)을 기준으로 서로 짝지어져 있다.
  • 예를 들어 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 인데 sqrt(36)이 되는 6을 기준으로 서로 데칼코마니처럼 짝을 이룬다. (4 X 9), (3 X 12), …
  • 따라서 약수가 있는지 검사할 때는 sqrt(N)까지만 검사해도 된다.
• count는 소수가 아닌 수를 세는 변수다.
  • 그리고 나중에 이를 모든 후보의 개수인 allComb.size()에서 빼주어 최종적인 소수의 개수가 되는 answer를 구했다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기