[백준] 2812번: 크게 만들기

2812번

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

어떻게 풀면 좋을까?

n번째 자리수가 n+1번째 자리수보다 작으면 빼 주면 된다.
그럼 자연스레 가장 큰 자릿수에 큰 수가 들어오게 될 것이다.
stack을 사용하자!

😂여기서 나는 하나를 빼먹었다. 이미 앞에서부터 큰 숫자로 채워져 있다면 K개를 지우지 않고 출력해 버리게 짠 것이다. 따라서 이런 경우를 방지하기 위해서, buckek[:N-K] 까지 출력해야 한다.

풀이

N, K = map(int, input().split())
number = list(input())

bucket = []
count = K

for i in number:
    while bucket and bucket[-1] < i and count > 0:
        bucket.pop()
        count -= 1
    bucket.append(i)
# 이미 앞에서부터 큰 숫자로 채워져 있다면 뒤에수는 짤라야 한다. 9873 하면 98로 나올 수 있게!
print(''.join(bucket)[:N-K])