문제 설명

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

입력 조건

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력 조건

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

코드

import sys
from collections import deque

n, k = list(map(int, sys.stdin.readline().split()))
num = list(sys.stdin.readline().rstrip())

# k개를 지워야 한다는 것은, n-k를 선택해야 하는 것과 동일한 의미다.
# 따라서 n-k 개를 선택하는 문제로 치환해서 푼다.
max_select = n - k

# 스택의 LIFO 특성을 이용하여 풀이한다. 앞자리에서 최대한 큰 수가 되있을수록 앞자리보다는 뒷자리에서 변동 가능성이 크다.
# 물론, 선택 횟수가 충분하고 나중에 나오는 수가 앞자리 수보다 크다면 앞자리 수도 변동 가능성이 충분히 있긴 하다.
stack = deque()

# 선택한 횟수
select = 0

answer = []

for i in range(len(num)):
    # 아직 남아 있는 숫자의 갯수
    yet = len(num) - i

    # 아직 남아있는 숫자들로 충분히 선택할 수 있다면,
    if yet > max_select - select:
        target = num[i]

        # 스택에 있던 요소들에 대해 확인해본다.
        while stack:
            top = stack[-1]
            # 만약 빼내도 수가 충분할 수 있고 맨 뒷 자릿수가 현재 수보다 작다면, 빼내고 선택 횟수를 줄인다.
            if yet > max_select - select and top < target:
                stack.pop()
                select -= 1
            # 그렇지 않다면, 빼내는 것을 중지하고 종료한다.
            else:
                break

        # 스택이 최대 선택만큼 차있지 않다면, 스택 맨 뒤에 수를 놓고 선택 횟수를 증가시킨다.
        if len(stack) < max_select:
            stack.append(target)
            select += 1
    # 아직 남아있는 수들로 앞자릿수들을 갱신할 수 없고, 스택이 최대 선택만큼 차있지 않다면, 뒷자리에 수를 채운다.
    elif len(stack) < max_select:
        stack.append(num[i])
        select += 1

print(''.join(list(stack)))