티스토리 뷰

728x90

문제

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

 

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

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

programmers.co.kr

 

 

풀이 및 소스코드

파이썬에서 제공하는 permutations라는 순열을 통해 쉽게 해결할 수 있었다.

permutations를 통해 후보들을 구한 후에 set 함수를 사용하여 중복을 제거해주었다.

from itertools import permutations
import math
def solution(numbers):
    answer = 0
    n = len(numbers)
    candis = []
    for i in range(1, n+1):
        per = permutations(numbers, i)
        for j in per:
            candis.append(int("".join(j)))
    candis = set(candis)
    answer = len(candis)
    for candi in candis:
        if candi == 0 or candi == 1:
            answer -= 1
            continue
        for i in range(2, int(math.sqrt(int(candi))+1)):
            if int(candi)%i == 0:
                answer -= 1
                break
    return answer
반응형