[プログラマ]大数の作成


これはスタックを利用する問題です.最初は組合せで解くだけで,予想していたがタイムアウトが発生した.先周笔记试験があって、しばらく休んで、结局卵が损をしました.だからすぐには解けなかった.(TMI..)
いずれにしても、スタックの解を利用するのはあまり得意ではないようです.問題に基づいてスタックを利用した解決策だと理解していますが、実際には適用されていません.
一番後ろの要素はfor回りにwhile回りに回ればいいのに、どうして思い出せないの...?とにかく問題の説明を始める
この問題と同様に,スタックを利用する問題を選択した.今週末コセットを見る前に必ず解いてみなければなりません.큰 수 만들기, 괄호변환, 같은숫자는 싫어, 나누어 떨어지는 숫자, 짝지어 제거하기, 문자열 압축

1.問題の説明



数字は数字の形で与えられる.このとき,文字列からk個の数字を削除したときに出現する可能性のある最大数を求めることができる.

2.難しいところ


1)組み合わせ


このような問題を見て、いつも思っているのは組み合わせです.もちろん組み合わせて解くことはできますが、タイムアウトが発生します.与えられた条件から見ると.number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.そう考えると当然タイムアウトが発生します.
def solution(number, k):
    order_list = set()
    for order in combinations(range(len(number)), k):
        temp = tuple(sorted(order))
        order_list.add(temp)

    result = []

    for pick_order in order_list:
        temp = ""
        for ord in range(len(number)):
            if not ord in pick_order:
                temp += number[ord]
        result.append(int(temp))

    return str(max(result))
タイムアウト

2)スタックで解く


スタックを使った感じがしましたが、ちょっと混同していました.ずっと考えてたけど...スタックを活用した解答はいつも混同される.
最初はスタックを宣言し、ワイルドカードを迂回して、スタックの最後の要素と現在のpのnumの数が大きいかどうかを確認し、戻ろうとしました.
このように編成すると,p値の処理はあいまいである.1回転ごとにp値を更新しますが、スタック内の最後の要素が比較オブジェクトより大きいことを確認し、p値を更新すると、次の要素が大きくなる可能性があります.
いつもこの部分を混同している.ループで比較し、インデックスをどのように処理しますか?ただし削除するとインデックスが混乱するので、スタックを個別に宣言して比較する必要があります.
要するに,スタックを単独で宣言するが,forループで要素を更新し,ループ内ループwhileループですべての条件を処理すると結論した.

3.解答

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

    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)

    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)