프로그래머스 level2 [소수 찾기] - 완탐

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

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

문제 설명

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

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

제한사항

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

입출력 예

numbers                                                                                                                         return

"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

1.  c++

모든 순열을 찾아내기 위해 next_permutation을 사용한다. (#<include>algorithm)

next_permutation을 사용하기 위해서는 우선 벡터를 정렬해주는 작업이 필요하다.

while문이 아니라 do-while문을 써준 이유는 다음 순열 존재 여부를 판별하는 next_permutation을 사용하기 때문에 첫번째 조합을 먼저 계산하고 while문으로 검사해야하기 때문이다.

 

또한, 모든 순열을 찾아냈을 때, ans벡터에 들어간 숫자 간 중복이 존재하기 때문에,

ans.erase(unique(ans.begin(), ans.end(), ans.end()) 코드를 통해 중복 원소를 제거해주는 작업을 해야한다.

unique를 사용할 때에도 먼저 벡터를 정렬해주는 작업이 필요하다.

 

그런 다음, 마지막으로 소수를 판별하는 방법인 '에스트라토네스의 체'를 통해 소수의 개수를 구해준다.

이는 해당 숫자의 제곱근까지만 해도 충분하다. (sqrt - cmath)

 

 

2. python

순열 이용해서 품

python의 순열 permutations

에스트라토네스의 체 -> 소수가 아닌것들을 제거하면서 푸는 방법. 배수를 이용한다.

정말 몇번째 까먹는건지 모르겠음

 

int(n**0.5) 

이부분 int로 감싸주지 않으면 float로 접근하기 때문에 TypeError 발생