📃 問題の説明

大数の作成

ある数字から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"
[質問元:プログラマー]

👨‍💻 解決策

私の考えは次から次へと広がってきた。

指定された文字の位置を変更せず、指定された位置のみ削除(?)
私たちは最大の数を創造しなければならないからです.
最大の数字に最大の値を出してみましょう.
指定した文字列の先頭に隣接する文字を比較します.
前の字が小さくなったら削除します.
だから"1924", k=2の場合.
“1”を削除して“924”になります
「2」を削除し、「94」になります.
2回削除すれば終了!(k=2)
しかしnumber[i]とnumber[i+1]を比較して解くとタイムアウトとなる.
削除を続行し、削除した文字列を再度削除します.
最初から比較していたので、不要な比較がたくさん出てきました.
例えば、文字列が"41777725"である場合
1と4が削除された後、「777725」になると、前の位置を比較する必要がなくなり、上記の方法で解くと、比較を続けます.文字列が長い場合はさらに深刻になります.
(999999…となると…)
そこで,스택を用いて解いた.
前から文字列をスタックに1つずつ入れます.
スタックのtopより大きい文字を入れる場合
スタックでpopを実行し、kを1つ削除します.
このプロセスはkが0になるまで実行される.
これにより、不要な比較を減らすことができます.

n/a.結論

文字列の前からスタックに1つずつ入れます.
スタックのtopより大きい文字を入れる場合はpopを実行します.
これにより、文字列の前からスタックに大きな値が順次積み重ねられるだけです.
kが0の場合、削除回数がいっぱいであることを示し、スタック内の値を文字列に変換して返すだけでよい.
ただし、kが0より大きい場合、文字列を返した後も削除される回数があります.
このとき後ろからk個削除すればいいです.
どうせ小数点以下はそのまま削除してから大数を生成します~
タイムアウト問題を解決するために悩むのは面白い.

👨‍💻 ソースコード

def solution(number, k):
    answerList = []

    for i in range(len(number) - 1):
        answerList.append(number[i])
        i += 1
        while len(answerList) > 0 and number[i] > answerList[-1] and k > 0:
            answerList.pop()
            k -= 1
    answerList.append(number[-1])

    if k > 0:
        answerList = answerList[:-k]

    return "".join(answerList)