小数点(プログラマの質問)Pythonの解答を検索します

11059 ワード

質問リンク:https://programmers.co.kr/learn/courses/30/lessons/42839
文字列numberを入力すると、numbersの要素(1または7以下)が新しい数に結合されます.組み合わせ可能な数のうち少数の数を見つけてリターンすることを目的としている.

説明する


1.最初

from itertools import permutations

def solution(numbers):
    answer = []
    for i in range(1, len(numbers)+1):
        map_num = list(map(''.join, permutations(list(numbers), i)))
        for j in map_num:
            if is_prime_number(int(j)):
                answer.append(int(j))
        
    answer = list(set(answer))
    
    return len(answer)

# 소수인지 아닌지 확인
def is_prime_number(number):
    if number < 2:
        return False
    elif number == 2: # 2일 경우는 소수가 맞음
        return True
    elif number % 2 == 0:
        return False
    for i in range(3, number, 2):
        if number % i == 0:
            return False
            
    return True
まず、数値文字列の数値で新しい数値を作成します.
このため、itertoolsのpremutationsをインポートし、map numにiビット数の配列を入れます.(入力が「123」、iが1、map numの値が[1,2,3]の場合)
次にmap numのインデックス値に少数の数を計算する必要があるため、is prime numberという関数を別途作成し、小数ではないことを確認し、小数であれば答え配列にappendを追加します.
最終的には、配列内の値が重複しないため、setとlistを使用して配列内部の重複データの除去を行い、配列内の個数を返します.

結果



しかし,時間的複雑さに問題が生じた.

2.2番目

from itertools import permutations

def solution(numbers):
    answer = []
    for i in range(1, len(numbers)+1):
        map_num = list(map(''.join, permutations(list(numbers), i)))
        for j in map_num:
            if is_prime_number(int(j)):
                answer.append(int(j))
        
    answer = list(set(answer))
    
    return len(answer)

# 소수인지 아닌지 확인
def is_prime_number(number):
    if number < 2:
        return False
    elif number == 2:
        return True
    elif number % 2 == 0:
        return False
    # number의 약수를 루트 number까지만 확인하면 됨
    root_number = int(number ** 0.5)
    for i in range(3, root_number+1, 2):
        # 소수가 아님
        if number % i == 0:
            return False
    return True
任意の数字nの約数の中で、自分以外の最大の約数は何ですか?
すなわち、ルートn以下である.
したがって,時間的複雑さの問題を解決するために,number値ではなくis prime number関数内部のfor文にroot number値を加えた.

結果



すべてのテストに合格しました.