백준 크게 만들기

문제

내가 생각했을때 문제에서 원하는부분

N자리 숫자가 주어졌을때
여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

내가 이 문제를 보고 생각해본 부분

자료구조 중에서 Deque를 사용하기로했다. 스택 과 큐의 설징을 갖는 데크가 
여러므로 도움이 될것같아 사용하게됐다.
데크가 비어있을 경우 input[i]를 맨 끝에 집어 넣는다.
데크가 비어있지 않을 경우, 데크의 맨 끝 요소와 input[i]에 대해 비교를 한다.
데크의 맨 끝 요소가 작을 경우 데크에서 없앤다.
2번이 만족하지 않을 경우, 2번 과정을 종료한다.
input[i]를 맨 끝에 집어 넣는다.

코드로 구현

package baekjoon.baekjoon_19;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

// 백준 2812번 문제
public class Main652 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        String input = br.readLine();

        char[] arr = input.toCharArray();
        Deque<Character> dq = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            while (K > 0 && !dq.isEmpty() && dq.getLast() < arr[i]) {
                dq.removeLast();
                K--;
            }
            dq.addLast(arr[i]);
        }

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

        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

시간복잡도 O(NK)

마무리

오늘은 간단하게 Deque를 사용해서 문제를 풀어봤다. 문제에 접근은 어렵게 느껴졌으나 생각해보면 간단한 문제였던것같다.