[백준] 크게 만들기

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

앞자리에 큰 숫자가 올수록 숫자가 커지게 됩니다. 따라서, 현재 자리수보다 높은 자리수에 있는 숫자가 더 작으면 필요 없는 숫자이므로 버립니다. 만약 그렇지 않으면 유지해줍니다. 버리는 숫자의 개수가 k개가 되거나 더이상 Deque에서 뺄 숫자가 없으면 버리는 행위를 중단합니다. 만약, 숫자가 내림차순으로 정렬되어 미처 버리지 못한 경우가 있을 수 있으므로 k가 남아있는 경우에는 끝에서 k개만큼 버려주면 됩니다. 

import sys
from collections import deque
# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n, k = tuple(map(int, input().split()))
nums = list(map(int, input().rstrip()))

bigger = []
dq = deque(nums)

while dq:
    if not bigger or bigger[-1] >= dq[0]:
        bigger.append(dq.popleft())
        continue

   # 마지막 자리수가 dq의 앞자리보다 작은 경우
    bigger.pop()

    k -= 1

    if not k:
        break

answer = ''.join(map(str, bigger)) + ''.join(map(str, dq))

if k:
    print(answer[:-k])
else:
    print(answer)