[BaekJoon] 2812 크게 만들기 (Java)

1.  문제 링크

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

2.  문제

요약

• N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 500,000보다 작거나 같은 N과 1보다 크거나 같고 N보다 작은 K가 주어지고 두 번째 줄에 N자리 숫자가 주어집니다.
  • 수는 0으로 시작하지 않습니다.
• 출력: 첫 번째 줄에 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N, K;
    static String numStr;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        K = scanner.nextInt();
        numStr = scanner.nextLine();
    }

    static void solution() {
        Stack<Integer> num = new Stack<>();
        int removeNum = removeSmallNum(num);
        if(removeNum < K) removeLastNums(num, removeNum);
        int size = num.size();
        for(int idx = 0; idx < size; idx++) sb.insert(0, num.pop());
        System.out.println(sb);
    }

    static void removeLastNums(Stack<Integer> num, int removeNum) {
        for(int idx = removeNum; idx < K; idx++)
            num.pop();
    }

    static int removeSmallNum(Stack<Integer> num) {
        int removeNum = 0;
        for(int idx = 0; idx < numStr.length(); idx++) {
            if(num.size() == 0 || removeNum >= K)
                num.push(numStr.charAt(idx) - '0');
            else {
                int cur = numStr.charAt(idx) - '0';
                while(num.size() > 0) {
                    int last = num.peek();
                    if(last >= cur || removeNum >= K) break;
                    if(last < cur) {
                        num.pop();
                        removeNum++;
                    }
                }
                num.push(cur);
            }
        }
        return removeNum;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch(IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch(IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

4.  접근

• 주어진 수의 첫 번째 수부터 마지막 수까지 반복문을 돌며 Stack에 수를 하나씩 넣는데, 현재 수가 Stack에서 뽑은 수보다 작거나 같을 때까지 Stack에서 수를 뽑은 후에(수를 지운 후에) 수를 Stack에 넣습니다.
• 위 과정을 통해 가장 높은 자릿수의 수를 제일 큰 수로 만듭니다.
• 위 과정을 통해 지운 수가 K개보다 작다면 위 과정을 통해 Stack에 있는 수들이 내림차순으로 정렬되어있기 때문에 높은 자릿수를 더욱 높게 만들 수 없으므로 1의 자릿수부터 K개가 지워질 때까지 지웁니다.