[알고리즘][X] 큰 수 만들기

문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

나의 풀이

- 틀린 풀이

- 10번에서 시간 초과가 난다.

- 재귀의 한계일지도...

- 재귀는 안쓰는게 옳다.

import sys
sys.setrecursionlimit(10000)

complete_number = ""
def solution(number, k):
    result_num = len(number) - k
    def recursive(number, num_complete_number):
        global complete_number
        if num_complete_number == result_num:
            return
        max_number = number[0]
        idx = 0
        for i, ele in enumerate(number):
            if ele == "9":
                max_number = "9"
                idx = i
                break
            elif max_number < ele:
                max_number = ele
                idx = i
        
        right_rest = len(number) - idx - 1
        if right_rest > (result_num - num_complete_number - 1):
            complete_number += number[idx]
            recursive(number[idx+1:], num_complete_number + 1)
        elif right_rest == (result_num - num_complete_number - 1):
            complete_number += number[idx:]
            return
        else:
            recursive(number[:idx], num_complete_number + len(number) - idx)
            complete_number += number[idx:]
    
    recursive(number, 0)
    return complete_number

- 참고한 풀이

- 제거할 수 있는 개수가 정해져 있는 것과 제일 앞의 자리가 중요하다는 게 핵심이다.

- 그리디는 O(n)으로 풀 수 있다.

def solution(number, k):
    stack = []
    
    for ele in number:
        # stack의 원소들을 제거할 수 있는 조건
        while len(stack) > 0 and stack[-1] < ele and k > 0:
            stack.pop()
            k -= 1
        stack.append(ele)
    
    if k > 0:
        stack = stack[:-k]
    return ''.join(stack)