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

접근

결국 N-K 길이의 숫자를 만드는 것은 동일하므로, 같은 길이의 숫자 중에서 가장 크기 위해서는 결국 맨 왼쪽에 오는 숫자가 가장 커야 한다. 따라서 N자리 수의 가장 왼쪽에서부터 오른쪽 수들과 하나씩 비교하며 작을 경우 지우면 된다. 스택에 저장하며 가장 마지막 숫자와 하나씩 비교하며 계산한다. 단, 모든 연산이 끝난 이후 1111 혹은 4321과 같이 k개를 다 지우지 못했을 경우에는 그만큼 뒤쪽에서 지워준다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ2812 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 입력값 저장
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        char[] input = br.readLine().toCharArray();

        // 스택에 저장하며 하나씩 비교
        Stack<Character> stk = new Stack<>();

        for (int i = 0; i < n; i++) {
            char cur = input[i];

            while (!stk.isEmpty() && stk.peek() < cur) {
                if(k == 0) break;
                k--;
                stk.pop();
            }

            stk.add(cur);
        }

        // 뒷자리에서 지워야하는 경우
        while(k > 0){
            stk.pop();
            k--;
        }

        // 스택에 저장된 문자를 출력하기 위해 StringBuilder에 저장
        while (!stk.isEmpty())
            sb.append(stk.pop());

        System.out.println(sb.reverse()); // 원하는 순서와 반대로 저장되어 있으므로
    }
}