[프로그래머스/파이썬] 그리디 큰 수 만들기

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])보다 지금 저장하는 수(i)가 크면 이전에 저장했던 수를 빼내고 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))