[Gold III] 크게 만들기 - 2812

문제 링크

분류

자료 구조, 그리디 알고리즘, 스택

문제 설명

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

입력

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

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

출력

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

풀이

N 자리 수에서 K개의 숫자를 뺏을때의 최대값을 구하는 문제이다. 스택을 이용해서 자릿수의 숫자를 하나씩 스택에 추가하는데, 스택에 추가하기 전에, 자신보다 작은 숫자들은 스택에서 빼는 방식으로 해결할 수 있다.

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

class Main {
   static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
   static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
   int N;
   int K;
   String NS;
   Deque<Integer> toPrint;
   int popCount;
   public static void main(String[] args) throws Exception {
       Main main = new Main();
       main.init();
       main.solution();
   }

   void init() throws Exception {
       int[] intArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
       N = intArray[0];
       K = intArray[1];

       NS = BR.readLine();

       toPrint = new ArrayDeque<>();
       popCount = 0;
   }

   void solution() throws Exception {

       for (int i = 0; i < N; i++) {
           int temp = Character.getNumericValue(NS.charAt(i));
           if (toPrint.size() == 0) {
               toPrint.add(temp);
           } else {
               if (popCount < K) {
                   while (toPrint.size() > 0 && popCount < K && toPrint.getLast() < temp) {
                       toPrint.removeLast();
                       popCount += 1;

                   }
                   toPrint.add(temp);

               } else {
                   toPrint.add(temp);
               }
           }

       }
       while (popCount < K) {
           toPrint.removeLast();
           popCount += 1;
       }
       for (Integer i : toPrint) {
           BW.write(Integer.toString(i));
       }
       BW.flush();
       BW.close();
   }
}