[백준] 2812: 크게 만들기 - JAVA

in Algorithm on 자료 구조

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

풀이

스택을 이용하는 그리디 문제였다.

N 자리 숫자에서 숫자 K 개를 지웠을 때의 최댓값을 구해야 한다.

숫자를 입력받으면서 stack에 하나씩 넣는다.

뺄 수 있는 개수(K)가 남아있고 stack의 끝값이 자신보다 작으면 그 값을 빼고 넣는다.

다만 N이 987654321과 같이 주어지면 stack에 들어가기만 하고 빠지는 숫자는 없다.

따라서 stack의 사이즈 - K 만큼 출력해 주어야 한다.

출력할 때 앞에서부터 빼기 위해서 stack 대신 deque을 이용했다.

메모리: 36464KB

시간: 380ms

언어: Java 11

코드

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

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());
        int K = Integer.parseInt(st.nextToken());

        Deque<Integer> dq = new ArrayDeque<>();
        String line = br.readLine();
        for (int i = 0; i < N; i++) {
            int now = line.charAt(i) - '0';
            while (!dq.isEmpty() && K > 0 && dq.getLast() < now) {
                dq.removeLast();
                K--;
            }
            dq.addLast(now);
        }

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

        System.out.println(sb);
    }

}