[백준] 2812번. 크게 만들기(JAVA)

문제

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

---

풀이(20분)

import java.util.*;
import java.io.*;

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());

        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 ans = new StringBuilder();
        while (dq.size() > K) {
            ans.append(dq.removeFirst());
        }

        System.out.println(ans);
    }

}

---

문제 풀이 전략

 

앞뒤에서 모두 제거해줄 수 있는 deque를 사용하여 문제를 해결한다.

만약 K > 0 (더 뺄 수 있는게 있음을 나타냄), dq가 비어있지않고, dㅂ의 마지막이 현재의 숫자보다 작다면 dq의 끝을 빼주고 k를 -- 하는 것으로 한다.

 

이는 단순하게 입력을 통해 최소의 수를 제거할 수 있게 해준다.