BOJ 2812 크게 만들기

https://www.acmicpc.net/problem/2812

문제

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

---

입력

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

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

---

출력

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

---

예제 입력 1

4 2
1924

예제 출력 1

94

예제 입력 2

7 3
1231234

예제 출력 2

3234

… 이하 예제 생략

---

코드

Stack은 Vector를 상속받아 구현한 것으로 Deprecated된 Vector를 사용하였기 때문에 Stack 대신에 Deque를 사용하도록 하자.

import java.io.BufferedReader;
import java.io.IOException;
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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()), K = Integer.parseInt(st.nextToken());
        Deque<Character> deque = new ArrayDeque<>();
        deque.push((char) br.read());
        for (int i = 1; i < N; i++) {
            Character input = (char) br.read();
            while (!deque.isEmpty() && deque.peek() < input && K > 0) {
                deque.pop();
                K--;
            }
            deque.push(input);
        }

        StringBuilder answer = new StringBuilder();
        int size = deque.size() - K; // K개를 전부 지우지 못했을 경우, 가장 작은 자리 숫자 K개를 출력에서 제외
        for (int i = 0; i < size; i++)
            answer.append(deque.pollLast());
        System.out.println(answer);
    }
}