[Programmers]Greedy-大きな数を作成(Python)

ソース

Greedy:大数を作成[Lv 2]

問題の説明

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

せいげんじょうけん

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

kは、1または複数のビット数未満の自然数である.

I/O例

numberkreturn"1924"2"94""1231234"3"3234""4177252841"4"775841"
 

Solution

説明する

def solution(number, k):
    number = list(number)
    for i in range(k):
        for j in range(len(number) - 1):
            
            if number[j] == '9':
                continue
            if number[j] == '0' or number[j] < number[j+1]:
                number.pop(j)
                break
        else:
            remain = k - i
            number = number[:-remain]
            break
    return str.join('', number)

結論を先に言えば失敗だテストボックスがタイムアウトしました.これは解決できない...
まず、私が解く方法を説明します.2のfor文を使って、それぞれnumberの数字を比較します.number[j]とnumber[j+1]を比較すると、number[j+1]がより大きい場合、number[j]を除去するように合計k個が除去される.
ドアをすばやく回転させるために、いくつかの状況をさらに減らすために、number[j]が9であれば、次の数字に直接ジャンプし、0であればキャンセルします.
中のfor文が正常に終了した場合、数字は最後まで比較され、k個も削除されなかった可能性があります.そのため、さらに減算された数(k-i)が必要となり、numberの末尾でグライダーが行われる.

結果

上図のように、8番の科学技術ボックスは長い時間を費やし、10番はタイムアウトした.

Best Code

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

グリディの問題ですがスタックを使いました.最初にスタックに要素を入れ、numberから1つずつインポートしてスタックの最後の要素と比較する方法.1つの要素を削除するたびに、kが削除され、kが0に等しい場合、すべて削除されます.
while文を使用すると、スタックに要素があり、kが0より大きく、スタックの最後の要素がnumberの値より小さい(num)、kが削除され、スタックの最後の要素が削除されます(pop()).whileゲートを出て、numをスタックに入れます.
以上のようにして、numをnumberの1番インデックス値から最後まで繰り返す.
for文が終了すると、kが0より大きいかどうかを比較します.0より大きい場合、スタックはk要素を最後から削除します.
スタックを文字列に変換し、対応する値を返します.

結果

この方法は私が解決した方法よりも効率的です.