[프로그래머스] 큰 수 만들기

link

def solution(number, k):
    answer = []
    for i in number:
        while answer and answer[-1] < i and k>0:
            answer.pop()
            k-=1
        answer.append(i)

    while k>0:
        k-=1
        answer.pop()

    return ''.join(answer)

문제를 풀면서 기존의 코드는 시간 초과가 발생하게 되었고

이는 그리디 알고리즘의 최선의 수를 생각하지 못한 이유였다.

결국 다른이들의 풀이를 찾아보게 되었고 이를 복기하기 위해 코드를 다시 설명한다.

문제에서 요구하는 것은

number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 이다.

설명

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

모든 코드를 순회하며 문자열을 모으고, 모으게 되는 answer 리스트의 제일 뒤 값이 순회중인 값보다 작다면 k 값을 줄이고 answer에 새로운 값을 추가하는 형태이다.

    while k>0:
        k-=1
        answer.pop()

해당 코드는 k 값이 0 보다 크지만, 모든 문자가 순회 되었을 때 제일 뒤의 값을 줄이며 문자열을 완성하는 구문이다.

참고 자료 https://scarletbreeze.github.io/articles/2019-07/pythonKit%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4(4)%ED%83%90%EC%9A%95%EB%B2%95%ED%81%B0%EC%88%98