큰 숫자 만들기

숫자 n에서 k개의 수를 제거해서 만들 수 있는 가장 큰 숫자를 구하라.

1234에서 숫자 두 개를 제거하면 [12, 13, 14, 23, 24, 34]를 만들 수 있습니다.

이 중 가장 큰 숫자는 34입니다. (숫자의 순서는 바뀌지 않습니다.)

 

• 숫자 n은 1자리 이상, 1,000,000자리 이하입니다.
• k는 1 이상, n의 자릿수 미만인 자연수입니다.
• 결과는 문자열로 출력합니다. 

[풀이]

1234에서 1, 2 처럼 앞뒤 숫자를 비교해서 앞 숫자가 작으면 지워주면 됩니다. 

자료구조를 이용한 풀이가 떠오릅니다만 식상한 감이 있으니 

특이하게 풀어야 주목 받으니 문자열로 풀어봅시다. 

 

def solution(number, k):
    length = len(number)
    final_length = length - k
    count = 0
    i = 0
    while i < length - 1:
        if number[i] < number[i+1]:
            number = number[:i] + number[i+1:]
            length = len(number)
            count += 1
            if i > 0:
                i -= 1
            if count == k:
                return number
        else:
            i += 1
    return number[:final_length]


print(solution("9824", 3))
print(solution("9824", 2))
print(solution("9824", 1))