문제

[백준] 크게 만들기 (Gold 3)

요약

N자리 숫자가 주어질 때, 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하라. (1 <= K < N <= 500,000)

분류

  • 그리디

풀이

1. 내 풀이 (그리디 알고리즘, 스택)

큰 수를 최대한 앞으로 보내고, 작은 수를 최대한 뒤로 보내는 것이 이 문제의 핵심이다. 스택을 이용해 이를 구현해보았다.

from collections import deque as dq
import itertools

n, k = map(int, input().split())
stack = dq()
arr = list(map(int, list(input())))
cnt = k
for val in arr:
    if len(stack) == 0:
        stack.append(val)
    elif stack[-1] < val and cnt > 0:
        while stack and stack[-1] < val and cnt > 0:
            stack.pop()
            cnt -= 1
        stack.append(val)
    else:
        stack.append(val)

print(''.join(map(str, list(itertools.islice(stack, 0, n - k)))))