큰 수 만들기

앞 자리에 큰 수가 오는 것이 전체를 크게 만든다. 따라서, 큰 것을 우선해서 골라 담고 싶다.
앞 자리에서부터 하나씩 골라서 담되, 지금 담으려는 것보다 작은 것들은 도로 뺀다. 단, 뺄 수 있는 수효에 도달할 때까지만

탐욕법

앞 단계에서의 선택 (앞 자리에 큰 수)이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality) 에 영향을 주지 않음

def solution(number, k):
    collected = [] #큰 수를 넣기 위한 리스트
    for i, num in enumerate(number): 
    #i = 지금 가리키고 있는 문자의 인덱스 num = 그 위치에 있는 글자
        while len(collected) > 0 and collected[-1] < num and k > 0:
            #collected라는 리스트에 원소가 하나 이상 있고
            #마지막 원소가 지금 담으려고 하는 문자인 num보다 작고
            #k가 0보다 크면
            collected.pop()
            k -= 1
        if k == 0:
            collected += list(number[i:])
        #만약 k가 0이라면 i자리에 있는 num부터 끝까지 collected에 이어 붙여라
            break
        collected.append(num)
    collected = collected[:-k] if k > 0 else collected
    # 뒤에서 k개만큼 빼낸다.
    # 빼낼 글자들을 다 빼내지 않았으면 끝에는 불필요한 글자들도 남아있다.
    # 그만큼 더 빼줘야 한다.
    answer = ''.join(collected)
    return answer