[プログラマー]少数を検索(Python)


質問する


問題の説明
一桁と書かれた紙片が散らばっている.ばらばらの紙切れを貼って、いくつかの小数点を作ることができることを見たいです.
各紙片の数字の文字シリアル番号を指定すると、紙片で作成できるいくつかの数を返すための解法関数を完了します.
せいげんじょうけん
numbersは、長さが1または7未満の文字列です.
numbersは0から9まで数字で構成されています.
「013」とは、0から3の数字の紙切れが散らばっていることを意味します.
I/O例
numbers return
"17" 3
"011" 2
I/O例説明
例1
[1,7]小数[7,17,71]を作成できます.
例2
[0,1,1]は小数点を作成することができる[1101].
11と011は同じ数字と見なされます.

解法


少数かどうかはともかく.まず、与えられた数字がいくつかの異なる数字を生み出すことができるかどうかを要求する.
1)
numbersの大きさnのようにnumbersの中の1つ2つを繰り返して言います...n個の抽出順序の組合せ.1ビット2ビット...n製造ビット数.
自ら実現しようとしたがタイムアウトしたため,最終的にモジュールㅠを用いた.
💡 Python itertoolsモジュール
  • 製品(p,q,...,[repeat=n]):デカルト乗
  • 置換(p,r):pからr個を抽出するシーケンス
  • 組合せ(p,r):pからr個を抽出する組合せ
  • 組合せwith置換(p,r):pからr個の繰返し組合せを抽出する
    Python APIドキュメントを参照
  • これらの関数はgeneratorであることに注目すべきである.すなわち,ループに値を投げ出すと,その値は記憶されない.したがって、これらの関数を作成した後、list()などで反復オブジェクトに値を含める必要があります.
    この問題でnumbersに同じ数字が含まれている場合、重複結果値が発生する可能性があるため、setに挿入して重複データ除去を行うことができます.
    (itertoolsモジュールとgeneratorの概念については、後で詳しく説明する必要があります)
    2)
    setの数字に対して小数であるか否かを判断する.
    💎 nが小数であると判断するときは、1と自分以外に小数があるかどうかを確認すればいいのですが、小数を求めるときは、nの平方根を確認すればいいのですが、以前のポスターにも書いてありました.(プログラマー-カーペット位置決め)

    🌈 完了コード

    from itertools import permutations
    import math
    
    def solution(numbers): 
        result = set()
        for n in range(1, len(numbers)+1):
            for p in permutations(numbers, n):
                result.add(int(''.join(p)))
                # permutations는 generator 이기 때문에 루프 한번 돌고 결과값 사라짐
                # set에 담기
                                
        answer = 0
        for num in result:
            check = 0
            if num < 2:
                check = 1  # 1이면 소수 아님
            elif num == 2:
                pass   # 2이면 소수임
            else:     
                for i in range(2, int(math.sqrt(num))+1):            
                    if num % i == 0:                
                        check = 1
                        break        
            if check == 0:            
                answer += 1
    
        return answer