소수찾기

 

 문제 설명

 

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

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

 

 제한 사항

 

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

 

 입출력 예

 

number return
"17" 3
"011" 2

 

 Python 코드

 

from itertools import permutations
def solution(numbers):
# 소수 판별할 리스트 만들기
num_list = [] # 전체 순열 넣어줄 리스트
for i in range(1,len(numbers)+1) :
test_list = permutations(numbers,i)
for j in test_list :
num_list.append(int("".join(j)))
num_list = set(num_list) # 중복과 0, 1 제외
if 0 in num_list :
num_list.remove(0)
if 1 in num_list :
num_list.remove(1)
# 소수 판별
answer = len(num_list) # 모든 수가 소수라 가정하고 시작
for i in num_list :
if i != 2 :
for j in range(2,int(i**0.5)+1) :
if i % j== 0 :
answer -=1
break
return answer

* 참고 링크 : https://mentha2.tistory.com/8

 

 C++ 코드

 

#include<string>
#include<vector>
#include<cmath>
using namespace std;
bool Visit[10000000];
bool Select[10];
int Answer;
bool IsPrime(int N)
{
if (N == 0 || N == 1) return false;
for (int i = 2; i <= sqrt(N); i++)
{
if (N % i == 0) return false;
}
return true;
}
void DFS(int Cnt, string S, string Res)
{
if(Res != "" && Visit[stoi(Res)] == false)
{
int Num = stoi(Res);
Visit[Num] = true;
if (IsPrime(Num) == true) Answer++;
}
for (int i = 0; i < S.length(); i++)
{
if (Select[i] == true) continue;
Select[i] = true;
DFS(Cnt + 1, S, Res + S[i]);
Select[i] = false;
}
}
int solution(string S)
{
DFS(0, S, "");
return Answer;
}

* 참고 링크 : https://yabmoons.tistory.com/336

 출처

 

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

+ Recent posts