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

💁🏻 나의 풀이

def solution(number, k):
    for _ in range(k):
        comb = []
        for i in range(len(number)):
            num = number[:i] + number[i+1:]
            comb.append(num)
        number = max(comb)
    return number

• 처음에는 그냥 combinations로 조합을 구해서 최대를 구하려고 했는데 전부 시간 초과남
• 그래서 탐욕법을 사용해서 숫자 1개를 뺄 때 가장 큰 수를 만드는 방식을 k번 돌리는 방식으로 풀이함
• 하지만, 이것도 몇 가지 케이스에 시간 초과가 됨

def solution(number, k):
    result = [number[0]]
    for i in range(1, len(number)):
        if number[i] > result[-1]:
            while result and result[-1] < number[i] and k > 0:
                result.pop()
                k -= 1
        result.append(number[i])
    result = result[:len(result) - k]
    return ''.join(result)

• 스택을 이용한 풀이 방식이 있다는 것을 참조해서 풀어봄
• 숫자의 각 자리에 대해 해당 숫자를 결과에 포함 시킬지 말지에 대한 선택을 매번 최선으로 하는 탐욕법을 통한 풀이임