[Gold III]
https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
풀이
한 달여만에 다시 잡은 알고리즘...
BFS 풀다 때려치고 Greedy로 도망침.
모든 숫자를 받아놓고.. 앞에서부터 하나씩, Stack에 넣어 가며,
K가 남아있는 한 앞에 있는 더 작은 숫자를 greedy하게 모두 pop하는 식으로 진행하면 complete.
from collections import deque
N, K = map(int, input().split())
num = deque(list(input()))
res = deque()
for _ in range(N):
a = num.popleft()
while len(res) > 0 and K > 0 and res[len(res)-1] < a:
res.pop()
K -= 1
res.append(a)
if K != 0:
while K > 0:
res.pop()
K -= 1
print(*res, sep="")