[プログラマー/Python]大きなGreedy数を作成

https://programmers.co.kr/learn/courses/30/lessons/42883

アルゴリズム分類

グリンディ

問題を解く

시간초과코드:

def solution(number, k):
    from itertools import combinations

    lst=list(combinations(number,len(number)-k))

    result=[]
    for i in lst:
        temp=("".join(i))
        result.append(int(temp))
    return (str(max(result)))

核心的な考え方は、前の位置を最大の数にすることです.
ex) numbers="54321", k=2
result=
['5', '4'] 2
['5', '4', '3'] 2
['5', '4', '3', '2'] 2
['5', '4', '3', '2', '1'] 2
現在保存されている数が以前保存されている数より大きい場合(result[1])、以前保存されている数を削除し、k-=1を実行します.
完了後にkが残っている場合、resultの後に残りの値を切り取って出力することができます.

참고: https://gurumee92.tistory.com/162

ソースコード

def solution(number, k):

    result=[number[0]]
    for i in number[1:]:
        while result and result[-1]<i and k>0:
            result.pop()
            k-=1

        result.append(i)

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

    return ("".join(result))