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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

완전 탐색, DFS

소수

 

set은 중복을 허용하지 않기 때문에 set에 수를 담는다.

---

 

코드

 

#include <string>
#include <set>
using namespace std;

set<int> mySet; // 중복되지 않는 숫자들을 저장하기 위한 집합
int ch[1000001]; // 방문 여부를 체크하기 위한 배열

bool Check(int x) // 소수를 판별하는 함수
{
    if (x <= 1) return false;
    if (x == 2 || x == 3) return true;
    if (x % 2 == 0 || x % 3 == 0) return false;

    for(int i = 5; i * i <= x; i++)
    {
        if (x % i == 0 || x % (i + 2) == 0) return false;
    }
    
    return true;
}

// 문자열로 가능한 모든 조합을 만들기 위한 깊이 우선 탐색(DFS) 함수
void DFS(string& numbers, string s, int x, int n)
{
    if(x == n){                
        return;
    }
    
    for(int i=0; i<n; i++)
    {
        if (ch[i] == 0)
        {
            ch[i] = 1; // 방문 표시
            // 현재까지 만들어진 문자열에 새로운 문자를 추가하고 집합에 삽입
            mySet.insert(stoi(s + numbers[i])); 
            DFS(numbers, s + numbers[i], x+1, n);

            ch[i] = 0; // 방문 표시 삭제
        }
    }
}

int solution(string numbers) {
    int n = numbers.size();

    DFS(numbers, "", 0, n); // DFS를 이용해 가능한 모든 숫자 조합을 만듬

    int answer = 0;
    // 집합에 저장된 모든 숫자에 대해 소수 판별을 실시
    for(const auto& num : mySet)
    {
        if (Check(num)) answer++; // 소수라면 카운트 증가
    }

    return answer; // 소수의 개수를 반환
}

 

 

---

 

소수 구하기 문제

 

2023.09.26 - [⭐ 코딩테스트/프로그래머스] - [프로그래머스 C++] 타겟 넘버

[프로그래머스 C++] 타겟 넘버

 

---