連続する整数値の中に「7」がいくつ出現するか数えるプログラムの高速化

投稿者: Anonymous

大学で行っているプログラミングの問題で「連続する整数値の中に出現する「7」がいくつあるかを数えてください。」という問題が出題されました。

例えば[7, 99]なら、「1,2,3,4,5,6,7」 と 「1,2,3,…,97,98,99」の数字の中にいくつ7が出現するかというもので、7なら1、99なら20という答えになります。
777が2個出現するので2個とカウントする。)
よって答えは[1, 20]という結果を1秒以内に表示しないといけないというのが課題です。

しかし、[99, 77777, 23678947, 732465890, 1912478368]この桁になると、処理速度が遅くて1秒を超えてしまい不可となってしまいます。
処理速度を早くするためにはどうすればよいでしょうか?Pythonでは限界があるのでしょうか?
コツとかがあれば是非教えてください!

import re
v = [99,77777,23678947,732465890,1912478368]
try:
    while True:
        v.append(input())
except EOFError:
    pass

for o in range(len(v)):
    x = v[o]
    z = []
    b = []
    d = 0
    w = int(x)

    for s in range(1,w+1):
        matchOB = re.findall("7",str(s))
        if matchOB:
            d += len(matchOB)

print(d)

解決

ものごとは分けて考えましょう。

「1からnまでの連続する整数値」のうち(以下A)、1の位には 7 はいくつでてくるでしょうか? n が 10 以上ならば、少なくとも int(n / 10) 回はでてきますよね? さらに n % 10 が 7 以上であれば、それに +1 回加えて登場するはずです。つまり n = 30 までなら 7, 17, 27 の 3回ですが、n = 37 ならば前の 3 つに 37 を加えて 4 回でてくるはずです。

では次に A のうち 10 の位には 7 はいくつでてくるでしょうか? n が 100 以上ならば、間違いなく int(n / 100) * 10 回はでてきます。n % 100 が 70 から 78 の時は、1の位の数字 +1 回が追加されますね。 n % 100 が 79 以上の時は +10 回となるでしょう。

同様に A のうち 1000 の位はどうなるでしょう? 10000 の位はどうでしょう? そうして一般化していけば、目的のプログラムができるでしょう。

def cnt7(v):
    return cnt7b(v, 1)

def cnt7b(v, b):
    if v < b:
        return 0
    bn = b * 10
    n = int(v / bn) * b
    m = int(v / b) % 10
    if m == 7:
        n += (v % b) + 1
    elif m > 7:
        n += b
    return n + cnt7b(v, bn)

def calc(v):
    print("%d -> %d" % (v, cnt7(v)))

for v in [99, 77777, 23678947, 732465890, 1912478368]:
    calc(v)
回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *