[Programmers] 완전 탐색 - 소수 찾기

프로그래머스 소수 찾기: 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은 같은 숫자로 취급합니다.

 

알고리즘 - 효율적인 소수 찾기 

• 주어진 수보다 작은 수들로 나눕니다.
• N/2까지 나눠지는 수가 있는지 확인합니다. 
• 루트 N까지 나눠지는 수가 있는지 확인합니다.  

참고 링크: https://myjamong.tistory.com/139

 

알고리즘 - 완전 탐색

완전 탐색은 다른 말로 브루트 포스법이라고 합니다. 브루트 포스(Brute-force, 난폭한/무식한 힘)라는 단어에서도 알 수 있듯이 단순하게 모든 경우의 수를 고려하는 것입니다.

참고 블로그: https://hongjw1938.tistory.com/78

 

제출 코드 

import itertools

def solution(numbers):
    '''
    numbers: 숫자 조합의 문자열 
    sosu_count: 소수인 숫자의 개수
    '''
    nums_lst = []
    sosu_count = 0
    
    for i in range(1, len(numbers)+1):
        tmp_lst = list((map(int, map(''.join, itertools.permutations(numbers, i)))))
        # print(tmp_lst)
        nums_lst = nums_lst + tmp_lst
        
    nums_lst = list(set(nums_lst))
    # print('전체 조합:', nums_lst)

    for num in nums_lst:
        if num <= 1:
            pass
            # print('1보다 같거나 작습니다.')
        else:
            for i in range(2, int(num**(1/2))+1):
                if num % i == 0:
                    break
            else:
                sosu_count += 1 
    
    return sosu_count

if __name__ == '__main__':
    nums = ['17', '011', '20']
    # answer = 3, 2, 1
    for n in nums:
        print(solution(n))

 

실행 결과

테스트 1 〉	통과 (1.04ms, 10.2MB)
테스트 2 〉	통과 (4.66ms, 10.4MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (3.01ms, 10.4MB)
테스트 5 〉	통과 (3.55ms, 10.9MB)
테스트 6 〉	통과 (0.04ms, 10.4MB)
테스트 7 〉	통과 (0.08ms, 10.4MB)
테스트 8 〉	통과 (3.73ms, 10.8MB)
테스트 9 〉	통과 (0.95ms, 10.4MB)
테스트 10 〉	통과 (6.92ms, 10.3MB)
테스트 11 〉	통과 (0.90ms, 10.4MB)
테스트 12 〉	통과 (0.25ms, 10.5MB)