[Day 3][コードテスト練習]欲張り法-大数をつくる

[コードテスト練習]貪欲法-製造大数

問題の説明
ある数字からk個の数字を削除しようとしたときに得られる最大の数字を取得しようとします.
たとえば、2つの数字が1924から削除された場合、[19,12,14,14,92,94,24]を作成することができる.このうち最大の数字は94です.
解関数のパラメータとして文字列形式で与えられた数値と削除する数値kを用いる.solution関数を完了し、numberからk個の数値を削除したときに作成できる最大数値を文字列で返します.
せいげんじょうけん

は、1桁より大きく、100000桁未満の数字です.

kは、1以上number의 자릿수未満の自然数である.

I/O例
numberkreturn"1924"2"94""1231234"3"3234""4177252841"4"775841"
ソース

大数の作成

サンプルの表示

小さいのを除いて、前は小さいのを除いて、後ろの小さいのは抜きません.

に道を教える

前の位置から一つ一つ取り出して盛り付けて、
今より小さい銀を持って帰る
ただし、減算可能な数(kkk)に達するまでは

大数は前列に、小数は後列に
(制約)K個の減算可能に制限

すなわち,右側にはもっと大きな数字が現れ,(k個)左の数字を減算できればよい.図には大きな数字7が現れ、1、4を順番に削除し、k-2になります.

インプリメンテーション

から与えられた数字のうち1つ1つを取り出して収集する.

このとき,現在出現しているものよりも収集したものを取り除く.

これはK個の

しか取れません

のように収集された数字は、ビット数で返されます.

がマイナス記号(k)を完了していない場合は

である.

桁はどのように計算されますか?

欲張り

貪欲法を適用できる.この言葉.

前段階での選択(上位の大数!)次のステップでの操作は、solutionの最適性に影響しません.

一番抜きたいのは欲張りな方法

def solution(number, k):
    collected = []
    for i, num in enumerate(number):
        while collected and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1

        if k == 0:
            collected = collected + list(number[i:])
            break

        collected.append(num)

    if k > 0:
        collected = number[:-k]
    return "".join(collected)