[Programmers] 소수 찾기

 

 

문제 

 

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

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

 

 

제한사항

 

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

 

코드 

 

import itertools
import math

def solution(numbers):
    arr = []
    answer = []
    idx = 0
    
    # numbers의 각 문자를 활용해서 나올 수 있는 모든 순열 구함. 
    for i in range(1,len(numbers)+1):
        num = list(map(''.join, itertools.permutations(numbers,i)))
        arr.append(num)
    
    # 2차원 배열 1차원 배열로 전환. 
    arr = sum(arr,[])
    arr = list(set(arr))
    
    # 배열 내 원소 중 첫 번째 문자가 0 이 아닌 경우만 정수형으로 전환해서 answer에 추가. 
    for k in arr:
        if k[0] == '0':
            continue
        else:
            answer.append(int(k))
    
    # 특정숫자가 2번 이상 반복될 경우 배열 내에 같은 수가 중복해서 존재하게 되기에 set로 바꿔줌. 
    answer = list(set(answer))
    
    # 소수를 판별할 경우 해당 수의 제곱근 이하까지만 나누어보면서 소수를 판별한다. 
    for z in answer:
        cnt = 0
        sqrt = int(math.sqrt(z))
        if z != 0 and z != 1:
            for j in range(2,sqrt+1):
                if z % j == 0:
                    cnt += 1
            if cnt == 0:
                idx += 1

    return idx

분석 > 거의 다 풀었을 때 계속 시간 초과가 나서 어디가 문제인지 찾는데에 시간이 꽤나 소요되었다. 결국 찾아낸 것은 소수를 1부터 자신보다 1 큰 수까지 모두 다 한 번씩 나눠보는 과정이 효율성을 저하시킨다 것이었다. 이번에 문제를 풀면서 알게된 것은, 소수를 판별할 때 자신의 제곱근 이하까지만 나누어서 나누어지는 횟수를 증가시키고 그 나누어진 횟수가 0이면 소수가 된다는 것이다. 24의 경우 2 * 12, 3 * 8, 4 * 6 으로 나타낼 수 있기 때문에 2,3,4 로만 나누어보아도 이 수가 6,8,12 로 나누어 떨어지는 지 알 수 있다는 것이다. 소수인 11의 경우 제곱근이 3.3XX 가 되기 때문에 3까지만 나누어보아도 이 수가 소수임을 알 수 있다. 이러한 특징을 활용해서 소수를 판별하려는 수가 0과 1이 아닐 때 2부터 자신의 제곱근 이하까지의 수로 자신을 나누어서 나누어 떨어지는 횟수를 통해 소수를 판별할 수 있다. 

 

 

* 참고한 글 

 

프로그래머스

 

 

 

 

 

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