[Inflearn] PS - 007

문제 출처 : inflearn <파이썬 알고리즘 문제풀이(코딩테스트 대비)>

가장 큰 수

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하
여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는
유지해야 합니다)
만약 5276823 이 주어지고 3개의 자릿수를 제거한다면
7823이 가장 큰 숫자가 됩니다.

▣ 입력설명
첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제가해야할 자릿수의 개수가 주어집니다.

▣ 출력설명
가장 큰 수를 출력합니다.

▣ 입력예제 1
5276823 3

▣ 출력예제 1
7823

▣ 입력예제 2
9977252641 5

▣ 출력예제 2
99776

풀이

'''
시작 : 12:45
종료 : 13:15

접근
1. Stack 구조 이용 - Last In First Out
2. 첫번째 숫자부터 리스트에 추가한다.
3. 이전에 들어간 숫자보다 작으면 들어간 숫자를 삭제하고, 크면 이전 숫자를 삭제한다.
4. 삭제된 숫자를 카운트해서, 주어진 n만큼만 삭제한다.
5. 만약 주어진 n보다 카운트가 작으면 완성된 리스트의 맨 뒷자리를 남은 n만큼 삭제한다.
'''

import sys
sys.stdin=open("input.txt", "r")

num, m = map(int, input().split())
num = list(map(int, str(num)))
stack = []

for x in num:
    while stack and m > 0 and stack[-1] < x:
        stack.pop()
        m -= 1
    stack.append(x)

if m != 0:
    stack = stack[:-m]

res = ''.join(map(str, stack))
print(res)