[백준](Java) 2812 - 크게 만들기

문제 링크

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

문제 풀이

원래는 숫자에 대해서 String으로 접근을 했는데 메모리 초과가 발생했다. 그래서 String에 대해서 사용하면 안되나? 라는 생각이 들었고 다른 사람들은 String을 썼는지, char형을 썼을지 찾는중에, 지금의 풀이에 영향을 받은 사람의 풀이를 보았다.

핵심은 char형과 deque였다. deque의 특성을 이용해서 순서대로 넣을수 있지만 맨 뒤에꺼를 다시 확인하거나 지울수 있기에 deque가 적합했던것 같다.

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        String num = sc.next();

        Deque<Character> dq = new ArrayDeque<>();
        char[] arr = num.toCharArray();
        dq.add(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            while (k > 0 && !dq.isEmpty() && dq.peekLast() < arr[i]) {
                dq.removeLast();
                k--;
            }
                dq.add(arr[i]);


        }
        StringBuffer sb = new StringBuffer();
        while (dq.size() > k) {
            sb.append(dq.pollFirst());
        }
        System.out.println(sb.toString());
    }
}