[pgs大数]GreedyアルゴリズムとStack

より大きなプログラマの作成
重複演算を減らす.

Greedy algorithm

あらゆる角度から最適な選択をする.これらの部分の選択が集まっていれば、全体的にも最適です.(=問題を一つ一つ解決しているようです)
授業表を並べて多くの授業を受ける問題では、前からいつも終了時間の一番速い授業で埋めたり、前から最大の数字を残したりして、前の数字を消します.これらの方法は,繰り返し適用できるアルゴリズムを指す.
実はアルゴリズムはこのように理解するより、問題に触れて問題を理解したほうがいいです...

Question

Solution

Solution 1

Greedyメソッドの一部として、以下のメソッドを作成し、kが保持されるまで繰り返し実行します.
常に前のk+1個の数字から最大の数字を選択します.
前の数字が飛ぶ.k-=失われた数
2)最大の数字がansに加算されます.
3)number[idx+1:]から上記操作を繰り返す.

def helper():
	nonlocal number, k, ans
        if len(number) == 1:
            number = str()
            k-=1
            return
        idx = 1
        max_val = int(number[0]) # 4, 7
        max_idx = 0 # 0, 2

        while idx <= k: # 1 <= 4
            if int(number[idx]) > max_val:
                max_val = int(number[idx])
                max_idx = idx
            idx += 1
        ans += number[max_idx]
        number = number[max_idx+1:]
        k -= max_idx

Solution 2

def sol2(number, k):
    
    stack = list(number[0])
    idx = 1
    
    while idx < len(number):
        if number[idx] > stack[-1]: # 증가한다면
            while stack and (stack[-1] < number[idx]) and k:
                stack.pop()
                k -= 1
        stack.append(number[idx])
        idx += 1
        if not k: break

    if k: return number[:-k] # 계속 감소하는 숫자일 경우 k가 남아있게 됨
    return ''.join(stack) + number[idx:]

比較結果

ソリューション1は良い方法ではありません.常にループで最大値(k+1個の数値)を検索し、比較して次のhelper()で同じ操作を繰り返すと、前のhelper()でループの部分を再び検索できます.
999888776,7のようにmaxが先頭であればk値は減少せず,最悪の場合O(n^2)の時間的複雑さを有する可能性がある.
解2はO(n)で処理した.範囲内で最大の数字を抽出し,前の数字を飛ばす概念は似ているが,スタックを用いて重複したプローブを除去できる.
「ソリューション1」は、回答を妨げるものではありませんが、次の時間制限を突破することはできません.重複演算を減らすために、もっと考えなければなりません.