[프로그래머스 level2] 소수 찾기
원래 알고리즘은 깃헙에만 업로드 했지만 기록용으로 벨로그에도 업로드를 해야겠다.
오늘 알고리즘 스터디하는 날인데 이래저래 핑계아닌 핑계로 미루고 미루다 급하게 풀었다!
[프로그래머스 level2] 소수 찾기
문제
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
접근 방법
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
완전 탐색인 문제이니까 어떻게 효과적으로 모든 경우를 체크할까 고민을 했다.
하지만 테스트 수를 보니까 상당히 작았다..!
-찌릿-
이건 순열 조합 써도 되겠다...!!
항상 순열 조합을 쓰고싶어 안달이 났었기에...!
그래서 순열을 통해 모든 나올 수 있는 수를 다 담고 set을 통해 중복의 수를 제거했다.
이후 for문을 통해서 소수를 판독하였다.
소수를 판독하는 알고리즘은 전에 과제로 좋은 효율을 내는 소수 판독 함수를 만들어서 적용했다.
풀이
from itertools import permutations
def isPrimeNumber(num):
if (num <= 1):
return False
divisor = 2
while (divisor < int((num ** 0.5) + 1)):
if num % divisor == 0:
return False
divisor += 1
return True
def solution(numbers):
numbers = [i for i in numbers]
answer = 0
perNums = []
setNums = []
for i in range(1, len(numbers) + 1):
perNums.append(list(permutations(numbers, i)))
for i in perNums:
for j in i:
temp = ""
for k in j:
temp += k
setNums.append(int(temp))
setNums = set(setNums)
for i in setNums:
if isPrimeNumber(i):
answer += 1
return answer
Author And Source
이 문제에 관하여([프로그래머스 level2] 소수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyotaek9812/프로그래머스-level2-소수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)