관리 메뉴

솜씨좋은장씨

[Programmers] 완전탐색 : 소수 찾기 (Python) 본문

Programming/코딩 1일 1문제

[Programmers] 완전탐색 : 소수 찾기 (Python)

솜씨좋은장씨 2020. 2. 28. 13:23
728x90
반응형

1일 1문제 22일차!

오늘의 문제는 프로그래머스의 완전탐색 소수찾기입니다!

 

코딩테스트 연습 - 소수 찾기 | 프로그래머스

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이

programmers.co.kr

itertools의 permutation함수와 이전에 풀었던 에라토스테네스의 체 문제를 활용하여 풀어보았습니다.

from itertools import permutations

def getPrimaryNum_Eratos(N): 
    nums = [True] * (N + 1) 
    for i in range(2, len(nums) // 2 + 1): 
        if nums[i] == True: 
            for j in range(i+i, N, i): 
                nums[j] = False 
    return [i for i in range(2, N) if nums[i] == True]



def solution(numbers):
    answer = 0
    
    num_list = list(numbers)
#     print(num_list)
    
    new_comb_list = []
    
    for i in range(1, len(num_list)+1):
        comb_list = list(permutations(numbers, i))
        
        for j in range(len(comb_list)):
#             print(comb_list[j])
            new_comb_list.append(int(''.join(comb_list[j])))
    
    new_comb_list = list(set(new_comb_list))
    
#     print(new_comb_list)
    
    max_num = max(new_comb_list)
    
    sosu_list = getPrimaryNum_Eratos(max_num+1)
    
#     print(sosu_list)
    
    for i in range(len(new_comb_list)):
        if new_comb_list[i] in sosu_list:
            answer = answer + 1

    return answer

permutations을 써야할부분에 combinations를 적어서 고민이 조금 되었지만 그래도 통과!

 

 

SOMJANG/CODINGTEST_PRACTICE

1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.

github.com

 

Comments