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

www.acmicpc.net/problem/2812

2812번: 크게 만들기

문제

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

입력

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

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

출력

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

---

풀이

스택의 성질을 이용

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
num = list(input().strip())
stack, temp = [], k
for i in range(n):
    while temp > 0 and stack and stack[-1] < num[i]:
        del stack[-1]
        temp -= 1
    stack.append(num[i])
print(''.join(stack[:n - k]))