큰 수 만들기

• BOJ의 크게 만들기와 동일한 문제.
• 차근차근 생각해보자. 가장 큰 수를 만들려면 맨 앞자리에 가능한 가장 큰 수를 배치해야 한다. 맨 앞자리에 올 수 있는 수는, 앞에서부터 k+1번째 까지의 수이다. 이중에서 가장 큰 수를 찾아서, 맨 앞자리에 배치한다. 가장 큰 수가 x번째에 있었다면, 이제 그 다음 자리에 올 수 있는 수는 x+1번째부터 k+2번째까지의 수이다. 이중에서 가장 큰 수를 찾아서, 두번째 자리에 배치하고.. 이런식으로 처리하면 된다.
• 이 작업은 스택을 이용하면 쉽게 구현할수 있다. i-1번째 숫자까지 사용해서 만든 가장 큰 수가 스택에 저장되어 있을때, i번째 숫자가 현재 만들어진 수의 마지막자리 숫자보다 크다면, 마지막자리 숫자를 지운다. 그 앞자리 숫자도 i번째 숫자보다 작다면 그 숫자도 지운다. 이렇게 반복해서, i번째 숫자보다 작은 숫자들을 모두 지운 다음 (스택에서 pop하고), i번째 숫자를 뒤에 붙이고 (스택에 push), i+1번째 숫자로 넘어가면 된다. 이때 지운 숫자의 갯수가 k가 되면 더이상 지우지 않고 그냥 스택에 바로 붙이는 것을 반복하면 된다.
• 이렇게 스택을 이용해서 구현했을때의 시간 복잡도는 O(n)이 된다

"""Solution code for "Programmers 42883. 큰 수 만들기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42883
- Solution link: http://www.teferi.net/ps/problems/programmers/42883
"""


def solution(number, k):
    stack = []
    removed_count = 0
    for ch in number:
        while stack and removed_count < k and stack[-1] < ch:
            stack.pop()
            removed_count += 1
        stack.append(ch)
    return ''.join(stack[:len(number) - k])