[백준 2812] 크게 만들기

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

---

입력

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

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

출력

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

---

예제 입력 3

10 4
4177252841

예제 출력 3

775841

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        st.nextToken();
        int K = Integer.parseInt(st.nextToken());
        Deque<Character> deque = new ArrayDeque<>();

        String num = br.readLine();
        char[] arr = num.toCharArray();

        for (char c : arr) {
            while (true) {
                if (K <= 0 || deque.isEmpty() || c <= deque.getLast()) {
                    break;
                }
                deque.removeLast();
                K--;
            }
            deque.addLast(c);
        }

        StringBuilder sb = new StringBuilder();
        while(deque.size() > K) {
            sb.append(deque.removeFirst());
        }

        System.out.println(sb);
    }
}

현재 숫자와 덱의 마지막숫자를 비교하면서 작으면 버리고 크면 넣는 방식을 이용하였다.